题面

题解

1. 单调栈经典例题，注意数据范围结果是long long
2. 题中要求做组成的面积最大，那么我们可以枚举每个高度所能组成的面积最大的长方形，然后取一个最大值即可
3. 就看题中的样例，对于高度为4的，只有左右两边的高度>=4 才能组成要枚举的长方形，那么就要求左右两边的小长方形高度最小为4，可以看到，左边没有，右边1个，所以面积为2*4=8
4. **那么转化就是，我们可以记录左边离他最近且小于它的高度的下标，右边离他最近且小于它高度的下标，那么（右-左-1）就是这个高度对应的最长的长度，**这不就是单调栈的应用嘛
5. 当然此题代码我还是用数组模拟栈，也可以用stack，具体看代码

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n, x;
unordered_map<int, int> mp;
int stkl[N], stkr[N], ttl, ttr;
int indexl[N], indexr[N];

int main() {

    while (cin >> n, n) {

        mp.clear();
        ttl = ttr = 0;

        for (int i = 1; i <= n; i++) {
            cin >> x;
            mp[i] = x;
        }
        
        for (int i = 1; i <= n; i++) {
            while (ttl && mp[stkl[ttl]] >= mp[i]) ttl--;
            if (ttl) indexl[i] = stkl[ttl];
            //如果ttl=0,说明左边所有高度都大于它，那么左边界就记为0
            else indexl[i] = 0;
            stkl[++ttl] = i;
        }

        for (int i = n; i > 0; i--) {
            while (ttr && mp[stkr[ttr]] >= mp[i]) ttr--;
            if (ttr) indexr[i] = stkr[ttr];
            //如果ttr=0，说明右边所有高度都大于它，那么有边界就记为n+1
            else indexr[i] = n + 1;
            stkr[++ttr] = i;
        }

        ll res = 0;
        for (int i = 1; i <= n; i++) {
            //注意数据范围，要转化成ll
            ll s = (ll) mp[i] * (indexr[i] - indexl[i] - 1);
            res = max(s, res);
        }

        cout << res << endl;
    }


    return 0;
}