博客

Poj 2559 最大矩形面积

题目来源

：

https://cn.vjudge.net/problem/POJ-2559#author=0


大意：给定一些长为1，高为x的连续矩形，求最大连续矩形面积


算法

：单调栈


题解


1. 开结构体，记录每个矩形的tl（高度），le（最大向左扩展长度）

2.

单调栈

，即u.tl>=h时，需弹出栈首的元素

3. 每次pop时，设变量k 此时维护弹出元素的le的和，maxx=max(maxx,u.tl*(k+u.le));

4. 不能再pop时，将{h[i],k+1}入栈；

5. 所有矩形输入完毕后，若！(!q.empty()),则依次pop直到栈空，重复3；

样例：7  2 1 4 5 1 3 3     ans=8;
入栈  2  S <2,1> 
        1   pop<2,1> k=0,ans=(2,0)=2;
            S <1,2>
        4 S<1,2> <4,1>
        5 S<1,2> <4,1> <5,1>
        1 pop <5,1> k=0; ans=(2,5)=5;k=1; 
          pop <4,1> k=1; ans=(5,8)=8;k=2;
          pop <1,2> k=2; ans=(4,8)=8;k=4;
          push<1,5>
        3 S <1,5> <3,1>
        3 pop<3,1> k=0;ans=(3,8)=8;k=1;
          push<3,2> 
push S<1,5> <3,2>
        pop<3,2> k=0,ans=(6,8);k=2;
        pop<1,5> k=2,ans=(7,8);k=7; 

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;
long long h[100001],n,m,maxx,k;
struct pp
{
    long long tl,le;
};
stack<pp>q;
void init()
{
    k=0;
    while(!q.empty()) q.pop();
    maxx=0;
}
int main()
{
    while(scanf("%lld",&n))
    {
        init();                 //多组数据，清空 
        if(n==0) return 0;
        for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
        q.push((pp){h[1],1});   //由于栈为空时不能取top，先加入一个元素 
        for(int i=2;i<=n;i++)
        {
            k=0;
            while(1)
            {
                pp u=q.top();
                if(u.tl>=h[i])
                {
                    maxx=max(maxx,u.tl*(k+u.le));//要先更新结果在维护k 
                    k+=u.le;
                    q.pop();
                }
                if(u.tl<h[i])
                {
                    q.push((pp){h[i],k+1}); 
            //由于k+1入栈，所以及维护了入栈元素的le又维护了其最大向右扩展 
                    break;
                }
                if(q.empty())
                {
                    q.push((pp){h[i],k+1});
                    break;
                }
            }
        }
        k=0;
        while(!q.empty())
        {
            pp u=q.top();
            maxx=max(maxx,u.tl*(k+u.le));
            k+=u.le; q.pop();
        }
        printf("%lld\n",maxx);
    }
}

附：

若是不明白为何k及维护le，又维护了ri；

可以理解为 某元素x 的le已经被维护好，因为是单调栈，此元素x 前比它高的矩形都已被pop掉，所以当前的k值维护了当前元素q——x间的距离，k+x.le即矩形的长