HDU 1506 Largest Rectangle in a Histogram(单调栈)

题目链接
题目大意：给一个直方图，在图中取一个矩形，使其面积最大。
??显然对于一个选定的矩形\(S\)来说，其高度取决于所选的直方图矩形中高度最低的那个矩形\(a_i\)，换句话说，在选定的面积\(S\)内对于这个高度最低的矩形\(a_i\)来说，没有比它更低的矩形了。所以我们可以用一个矩形，看它能向左向右扩展到哪里，就能得到包括这个矩形\(a_i\)的最大面积\(S\)。至于选定区间的左右端点，可以用单调栈来求出，方法与这道题类似。

const int maxn = 1e5+10;
int n, arr[maxn], l[maxn], r[maxn];
stack<int> sk, clears;
int main(void) {
    while(~scanf("%d", &n) && n) {
        for (int i = 1; i<=n; ++i) scanf("%d", &arr[i]);
        for (int i = 1; i<=n; ++i) {
            while(!sk.empty() && arr[sk.top()]>=arr[i]) sk.pop();
            l[i] = sk.empty() ? 1 : sk.top()+1;
            sk.push(i);
        }
        sk = clears;
        for (int i = n; i>=1; --i) {
            while(!sk.empty() && arr[sk.top()]>=arr[i]) sk.pop();
            r[i] = sk.empty() ? n : sk.top()-1;
            sk.push(i);
        }
        sk = clears;
        ll ans = 0;
        for (int i = 1; i<=n; ++i) ans = max(ans, (ll)arr[i]*(r[i]-l[i]+1));
        printf("%lld\n", ans);
    }
    return 0;
}

HDU 1506 Largest Rectangle in a Histogram(单调栈)

原文：https://www.cnblogs.com/shuitiangong/p/12723454.html