python/TangDou/LanQiaoBei/LanQiao14ShengSai/4_Stack.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 10000010;

int a[N];
int res;
/*
测试样例I
6
3 2 1 4 5 2

输出:
8

测试样例II
5
2 4 3 4 5

输出:
12
*/
int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    stack<int> stk;
    for (int i = 0; i <= n; i++) {                   // 注意：这里是0~n,其实数组中有效数据是0~n-1,之所以最后要多枚举一个n,是因为栈内可能存在一直找不到右手边比自己小的数据，最后补一个0，让它们都出栈
        while (stk.size() && a[i] <= a[stk.top()]) { // 栈不为空，并且，当前柱子高度小于栈顶柱子高度,此时，栈顶柱子找到了右手边的最远距离
            int h = a[stk.top()];                    // 栈顶柱子高度
            stk.pop();                               // 栈顶柱子出栈
            /*
            举例子：当前i=6，那么右边界是5。左侧有两种情况：
            1、栈里还有元素，那么stk.top()就是左侧的第一个比当前元素小的位置，比如是3，那么5-3=2，
            也就是当前元素向左是3（不包3），
            向右到5（包含5），那么就是【4，5】两个位置
            2、栈里没有元素，此时，找到右边界是5，左侧起点就是0，共【0,1,2,3,4,5】共6个，也就是i
            */
            int w = (stk.size() == 0 ? i : i - 1 - stk.top());
            res = max(res, h * w);
        }
        stk.push(i);
    }

    cout << res << endl;
    return 0;
}