思路:用单调队列分别求矩阵左右两边小于其高度的矩阵位置,将其右位置减去左位置乘以高度,结果就是遍历取最大值。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int h[N], l[N], r[N]; //h表示每个矩形高度,l和r分别表示矩形能向左右两侧扩展的边界
int q[N]; //q储存单调栈
int main()
{
while (scanf("%d", &n), n)
{
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
h[0] = h[n + 1] = -1; //保证矩形左右两侧一定有小于它高度的矩形,即保证栈非空
//可省去判断条件tt >= 0
//求左边界
int tt = 0; //tt表示栈顶
q[0] = 0;
for (int i = 1; i <= n; i ++ )
{
while (h[q[tt]] >= h[i]) tt -- ; //往左找到第一个比h[i]小的位置为止
l[i] = q[tt]; //记录第一个比h[i]小的矩形的位置
q[ ++ tt] = i; //添加当前矩形到栈中
}
//求右边界
tt = 0;
q[0] = n + 1;
for (int i = n; i; i -- )
{
while (h[q[tt]] >= h[i]) tt -- ;
r[i] = q[tt];
q[ ++ tt] = i;
}
LL res = 0;
for (int i = 1; i <= n; i ++ )
res = max(res, (LL)h[i] * (r[i] - l[i] - 1)); //更新矩形最大值
printf("%lld\n", res);
}
return 0;
}