欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

51nod 1102 面积最大的矩形(单调栈)

程序员文章站 2022-11-08 22:10:22
51nod 1102 面积最大的矩形(单调栈) 以i所指的矩形高度作为要组成的矩形的高度,分别向左右扩展。用单调栈维护一个left数组和一个right数组,记录向左右能扩展到的边界,然后扫一遍出结果...

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;
}