POJ 2559 （单调栈）

发表于 | 分类于 | 阅读次数：

单调栈的经典例题，虽然单调栈的题目已经做过一些了，但是还是在这卡了一会。

题目链接

题意

求最大矩形的面积。

思路

用一个单调栈存储一个单调递增的序列，用来查看每个矩形向左延伸的左边界。

单调栈中是一个单调的序列，所以我们在向左找的时候，就一直找就行。

注意的是，单调栈中存的是下标，不是值。

我们比较栈顶元素和当前元素的大小，直到遇到一个栈顶的元素小于当前元素，那么栈顶元素 +1就代表了左边界的位置。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <cstring>
#include <stack>
using namespace std;
typedef long long LL;
LL l[100005];
LL r[100005];
LL a[100005];
int main()
{
    int n;
    while(cin >> n && n)
    {
        stack<LL>S;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lld",&a[i]);
            while(!S.empty() && a[S.top()] >= a[i]) S.pop();
            l[i] = S.empty()? 1 : (S.top() + 1);
            S.push(i);
        }
        stack<LL>S1;
        for(int i = n ; i >= 1; --i)
        {
            while(!S1.empty() && a[S1.top()] >= a[i]) S1.pop();
            r[i] = S1.empty()? n : (S1.top() - 1);
            S1.push(i);
        }
        LL maxer = -1;
        for(int i = 1; i <= n; ++i)
        {
            maxer = max(maxer, (r[i] - l[i] + 1) * a[i] );
        }
        cout << maxer << '\n';
    }

}
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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <cstring>
#include <stack>
using namespace std;
typedef long long LL;
pair<LL,LL>P;

int main()
{
    stack<pair<LL,LL> >S;
    int n;
    long long t;
    while(cin >> n && n)
    {
    LL ans = -1;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lld",&t);
        LL width = 0;
        while(!S.empty() && S.top().first > t)
        {
            LL th = S.top().first;
            LL ts = S.top().second;
            S.pop();
            width += ts;
            ans = max(ans, width * th);
        }
        S.push({t,width + 1});
    }
    int temp = 0;
    while(!S.empty())
    {
        ans = max(ans, S.top().first * (S.top().second + temp));
        temp += S.top().second;
        S.pop();
    }
    cout << ans << '\n';
    }

}