HDU 1506 Largest Rectangle in a Histogram

Description

可以理解为：在一幅柱状图里找出最大的矩形

也可以理解为：找一个最大的矩形去覆盖柱子且不能覆盖空白处

单调栈功能

1.利用单调栈，可以找到从左/右遍历第一个比它小/大的元素的位置

2.以自己为最小或最大值找到最大的区间(对应 单调递增/单调递减)同1.

3.给定一个区间，找到这个区间的最大或最小值

此题用到了功能2，功能2是在1的基础上的

单调栈的维护是 O(n) 级的时间复杂度，因为所有元素只会进入栈一次，并且出栈后再也不会进栈了。

Code

#include <stack>
#include <cstdio>
#include <iostream>
using namespace std;
#define ll long long
const int N = 100100;

ll h[N];
int L[N], R[N];
stack<int> sk;

///单调栈维护了一个单调递增序列，但它栈内元素甚至连单调都算不上
///单调栈:栈内越靠近栈顶的下标所对应的高度越高
///但栈内所存的，终究还是下标
int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        for(int i = 0; i < n; ++i)
            scanf("%lld", &h[i]);

        while(!sk.empty())
            sk.pop();

        for(int i = 0; i < n; ++i)
        {
            while(!sk.empty() && h[sk.top()] >= h[i])
                sk.pop();

            if(sk.empty())
                L[i] = -1;
            else
                L[i] = sk.top();
            sk.push(i);
        }

        while(!sk.empty())
            sk.pop();

        for(int i = n - 1; i >= 0; --i)
        {
            while(!sk.empty() && h[sk.top()] >= h[i])
                sk.pop();

            if(sk.empty())
                R[i] = n;
            else
                R[i] = sk.top();
            sk.push(i);
        }

        ll ans = 0;
        for(int i = 0; i < n; ++i)
            ans = max(ans, h[i] * (R[i] - L[i] - 1));
        cout << ans << '\n';
    }
    return 0;
}