直方图中最大的矩形

AcWing-131-直方图中最大的矩形

分析

见《进阶指南》第53页。

栈内记录的是元素的下标。

实现

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 100010;
int n, h[N], l[N], r[N];
stack<int> s;

void solve () {
    // 左边界
    while (!s.empty()) s.pop();
    for (int i = 1; i <= n; ++ i) {
        int cur = i;
        while (!s.empty() && h[s.top()] >= h[cur]) s.pop();

        if (!s.empty())
            l[i] = s.top() + 1;
        else
            l[i] = 1;
        s.push(cur);
    }
    
    // 右边界
    while (!s.empty()) s.pop();
    for (int i = n; i >= 1; -- i) {
        int cur = i;
        while (!s.empty() && h[s.top()] >= h[cur]) s.pop();

        if (!s.empty())
            r[i] = s.top() - 1;
        else
            r[i] = n;
        s.push(cur);
    }
}

int main () {
    while (cin >> n && n) {
        for (int i = 1; i <= n; ++ i) scanf("%d", &h[i]);

        solve();
        LL res = 0;
        for (int i = 1; i <= n; ++ i)
            res = max(res, (LL)h[i] * (r[i] - l[i] + 1));
        cout << res << endl;
    }
    return 0;
}