(单调栈)Largest Rectangle in a Histogram

之前写hdu1505的时候居然用错误的算法给水过去了（实际上那个题目从高度1开始枚举，我那个记录每个元素id的做法好像也行）

但这个题目记录id就不行了，导致wa了1个小时才发现问题。。。

由于之前记录的id会被pop，可能导致答案减小，所以必须通过合并矩阵和记录宽度来保存状态

单调栈很简单就不多写了

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define AC return 0
using namespace std;
double pi = acos(-1);
const double eps = 1e-12;
const int maxn = 1e5 + 10;


stack<pair<ll, ll > >stk;

int main()
{
    //freopen("C:\\E.in", "r", stdin);
    ll n;
    while (~scanf("%lld",&n), n)
    {
        while (!stk.empty())stk.pop();
        ll ans = 0;
        for (ll i = 1; i <= n; i++)
        {
            ll x;
            scanf("%lld", &x);
            if (stk.empty() || x > stk.top().first)
            {
                stk.push({ x,1 });
            }
            else
            {
                ll widnow = 0;
                while (!stk.empty() && x < stk.top().first)
                {
                    ll vue = stk.top().first, wid = stk.top().second;
                    widnow += wid;
                    ans = max(ans, vue * widnow);
                    stk.pop();
                }
                stk.push({ x , widnow + 1 });
            }
        }
        ll wid = 0;
        while (!stk.empty())
        {
            wid += stk.top().second;
            ll vue = stk.top().first;
            stk.pop();
            ans = max(ans, wid * vue);
        }
        printf("%lld\n", ans);
    }
    AC;

}

(单调栈)Largest Rectangle in a Histogram

原文：https://www.cnblogs.com/ruanbaiQAQ/p/13387684.html