思路

用一个单调递增栈保存当前位置左侧的、高度小于等于当前位置柱子高度的位置索引。找最大矩形面积即找以各柱子高度为高的最大矩形面积中的最大值。遍历整个高度数组，对于以当前柱子高度为高的矩形，最大面积即为最大横坐标跨度，左边界索引为stk[top-1]（栈单增，stk[top-1]是左边第一个高度小于或等于栈顶元素的位置），右边界索引为i-1（i是第一个比栈顶元素矮的柱子，故i-1是最后一个高度大于或等于栈顶元素的位置），对于每个弹出的栈顶元素，使用其高度和上述计算的宽度来计算面积，并更新记录的最大面积

注意

1.数据溢出

2.遍历完直方图时，栈中可能还有剩余元素需要处理

3.每轮需初始化重置栈和最大面积

4.只在栈顶元素出栈时更新最大面积(出栈说明右边界已找到或已遍历至末尾，而左边界由单调栈保存，此时计算的面积才是以各柱高为高的最大矩形面积)

代码

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

const int N = 1e5 + 10;
long long int square[N], stk[N], top = 0;
// 存储矩形最大面积 注意数据溢出
long long int S = 0;

int main()
{
    int n;
    while (1)
    {
        cin >> n;
        // 结束输入
        if (n == 0)
            break;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &square[i]);

            // 单调递增栈 存储下标
            // 如果当前矩形高度小于栈顶矩形高度 弹出栈顶元素 计算以栈顶元素为高度的最大面积(长度为i-1-stk[top-1])

            // 分析长度为i-1-stk[top-1]:
            // 栈顶元素的右边界是 i - 1（因为 i 是第一个比栈顶元素矮的柱子，所以 i - 1 是最后一个高度大于或等于栈顶元素的位置）
            // 栈顶元素的左边界是 stk[top - 1]（因为栈是单调递增的，所以 stk[top - 1] 是左边第一个高度小于或等于栈顶元素的位置）
            while (top && square[stk[top]] >= square[i])
            {
                S = S >= (i - 1 - stk[top - 1]) * square[stk[top]] ? S : (i - 1 - stk[top - 1]) * square[stk[top]];
                top--;
            }
            stk[++top] = i;
        }
        // 处理栈中剩余元素
        while (top)
        {
            S = S >= (n - stk[top - 1]) * square[stk[top]] ? S : (n - stk[top - 1]) * square[stk[top]];
            top--;
        }
        cout << S << endl;
        // 重置以便下轮循环使用
        top = 0;
        S = 0;
    }
    return 0;
}