HDU 1506（单调栈）

题意

  给出一个长度为n的序列，这些序列代表每个宽度为1的矩形的高，矩形是按顺序连在一起的，问最大相连面积（高为相连矩形的最小）。

解题思路

  对于每个最大连续的矩阵区间，如果它的边界有比这个区间最矮的矩形高的矩形，那么高的矩形肯定会被合并进去的，这与假设相违背，则对于每个最大区间，其区间最矮的矩形肯定是比相邻矩阵高的大。即找到每个节点的从左（从右）第一个比它小的节点，这样就是当前节点能构成的最大连续矩形，我们就能用单调栈解决。最后递推出最大值就行了。注意边界的处理。

代码

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            佛祖保佑       永无BUG
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
stack<int> s;

int l[maxn],r[maxn],arr[maxn];
int main()
{
#ifdef DEBUG
    freopen("in.txt","r",stdin);
#endif // DEBUG
    int n;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1; i<=n; i++) scanf("%d",&arr[i]);
        while(!s.empty()) s.pop();
        for(int i=1 ; i<=n ; i++)
        {
            while(s.size() && arr[s.top()] >= arr[i]) s.pop();
            if(s.empty()) l[i] = 0;
            else l[i] = s.top();
            s.push(i);
        }
        while(!s.empty()) s.pop();
        for(int i=n ; i>=1 ; i--)
        {
            while(s.size() && arr[s.top()] >= arr[i]) s.pop();
            if(s.empty()) r[i] = n+1;
            else r[i] = s.top();
            s.push(i);
        }
        long long ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,(long long)arr[i]*(r[i]-l[i]-1));
        printf("%lld\n",ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60