视频题解 131. 直方图中最大的矩形（每日一题·春季） - AcWing
单调栈（存放可能作为答案的数，只能越来越大） 求每个数左边最近的比它小的数的下标
基于y总的代码：
//对y总视频题解的中的代码，加了一点点注释
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100000+5;
//h[N]记录矩形高度,l[N]记录矩形左边最近的高度小于自己的下标,r[N]记录矩形右边最近的高度小于自己的下标
//q[N]记录所有可能作为答案的数的下标，该栈必然单调
int h[N],l[N],r[N],q[N];
int main(){
int n;
while(scanf("%d",&n),n){
for(int i = 1;i <= n;i++) scanf("%d",&h[i]);
h[0] = h[n + 1] = -1;
int tt = 0; //单调栈栈顶指针
q[0] = 0;
for(int i = 1;i <= n;i ++){
while(h[i] <= h[q[tt]]) tt --;
l[i] = q[tt];
q[++ tt] = i;
}
tt = 0;
q[0] = n + 1;
for(int i = n;i >= 1;i--){
while(h[i] <= h[q[tt]]) 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;
}