POJ2559 POJ2082（单调栈）

February 05, 2016

POJ2559 题目链接

题意：求出一些小矩形组成的图片的最大矩形面积。

思路：设所求矩形为 L，枚举 L 的右边界，在每次枚举中再枚举 L 的高度。通过一个单调栈（不减）来实现。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int h[100555];
int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(scanf("%d", &n)!=EOF && n){
        stack<int> s;
        for(int i = 1; i <=n; i++)
            scanf("%d", &h[i]);
        s.push(0);
        h[n+1] = 0;
        long long ans =0;
        for(int i = 1; i <=n+1; i++){
            while(h[i] < h[s.top()]){
                int a = h[s.top()];
                s.pop();
                int b = i-s.top()-1;
                long long tem = (long long)a*b;
                if(ans < tem)
                    ans = tem;
            }
            s.push(i);
        }
        cout << ans << endl;
    }
    return 0;
}

WA 了几发的原因是，当 s.top()作为所求矩形高时，所求矩形的长不是从这个矩形到 i 的长度，而应该是栈中前一个元素的右边的矩形到 i 的长度。

POJ2082 题目链接

一样的题，只不过长不是 1 了，是给定的。

看讨论版有人说 O（n^2）也能过，果断暴力了一发，然后 T 了，老老实实的写单调栈。。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int h[50005];
int l[50005];
int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(scanf("%d", &n)!=EOF && n!=-1){
        int ans = 0;
        l[0] = 0;
        for(int i = 1; i <= n; i++){
            int f;
            scanf("%d%d", &f, &h[i]);
            l[i] = l[i-1]+f;
        }
        //for(int i = 1; i <= n; i++)cout << l[i] << endl;
        stack<int> s;
        s.push(0);
        h[++n] = 0;
        for(int i = 1; i <= n; i++){
            while(h[i] < h[s.top()]){
                int a = h[s.top()];
                s.pop();
                int b = l[i-1]-l[s.top()];
                int tem = a*b;
                //cout << "a:" <<a << "b:" << b <<endl;
                //cout << tem <<endl;
                if(tem > ans)
                    ans = tem;
            }
            s.push(i);
        }

        cout << ans << endl;
    }
    return 0;
}