51nod 1102 面积最大的矩形（单调栈）

51nod 1102 面积最大的矩形（单调栈）

以i所指的矩形高度作为要组成的矩形的高度，分别向左右扩展。用单调栈维护一个left数组和一个right数组，记录向左右能扩展到的边界，然后扫一遍出结果。

#include 
#include 
#include 
using namespace std;

const int maxn = 5e4+10;
long long num[maxn];
int lt[maxn],rt[maxn];

int main()
{
    int n;
    cin >> n;
    num[1] = 0;
    for(int i = 2; i <= n+1; ++i)
        cin >> num[i];
    num[n+2] = 0;
    n += 2;
    stack s1,s2;
    for(int i = 1; i <= n; ++i)
    {
        while(s1.size() && num[s1.top()] >= num[i])
            s1.pop();
        if(s1.size()) lt[i] = s1.top()+1;
        else lt[i] = i;
        s1.push(i);
    }
    for(int i = n; i >= 1; --i)
    {
        while(s2.size() && num[s2.top()] >= num[i])
            s2.pop();
        if(s2.size()) rt[i] = s2.top()-1;
        else rt[i] = i;
        s2.push(i);
    }
    long long res = 0;
    for(int i = 1; i <= n; ++i)
        res = max(res,(rt[i]-lt[i]+1)*num[i]);
    cout << res << endl;
    return 0;
}