最大矩形-HDU1506
题目链接：[Problem - 1506 (hdu.edu.cn)]
1.高度序列在相同时，最大的矩形很好算：
i=1 s=h*1
i=2 s=h*1+h*1
i=3 s=h*1+h*1+h*1
... ...
也就是s=高度*数组长度
2.高度不同，但是单调增时：
算了第五列一列的面积之后，由于第四列可以“延伸”到第五列所以第四列的宽度要更新为2。
同理第三列宽度为3，第二列宽度为4，第一列宽度为5。
根据这个性质，可以维护一个栈顶到栈底递减的单调栈。
3.以以下数据作为例子：
1=> 4入栈，对应宽度置1
2=> 2入栈会破坏栈递减的单调性，4出栈并且更新“ans”为4，2入栈宽度更新为2
3=> 3入栈
4=> 2入栈会破坏栈递减单调性，之前的2,3出栈，这个2宽度更新为4
5=> 5入栈
至此，我们得到的图就变成了这样：(高度为2长度为4和高度为5，长度为1)
最后我们只要将0压入队列，就能更新出需要的答案。
因为0是高度中最小的，将0压栈等于把栈内全部元素弹栈，在弹栈的过程中就更新了ans值。
总结
整个过程很像是在将数列中“高挑”的数字减少到和周围齐平。意会一下8。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 1e6+10;
typedef long long ll;
using namespace std;
int n;
int a[N],w[N],stk[N];
void solve(){
int p=0;
ll ans=0;
rep(i,1,n+1){
int width = 0;
while(p && a[i]<=stk[p]){
width+=w[p];
ans=max(ans,(ll)stk[p--]*width);
//要注意ans是ll，要用（ll）强制转换
}
stk[++p]=a[i];
w[p]=width+1;//延申到前面的宽度要加上自己的宽度
}
printf("%lld\n",ans);
}
int main(){
while(scanf("%d",&n)){
if(!n)return 0;
memset(a,0,sizeof a);
memset(w,0,sizeof w);
memset(stk,0,sizeof stk);
rep(i,1,n)scanf("%d",&a[i]);
solve();
}
}