（原题：poj2559）
经过几个月的疫情，很多小门店已经撑不住高额的租金了。这下 HZOI 帝国又要招商了，帝国策划员小A（跟出游的小A无关）打算刷一个海报。
他在市里找了一个适合刷海报建筑群，它包含 N个紧靠着的形状规则的矩形建筑，从左到右，高度依次为h1,h2,h3... ，宽度均为1 。
小A要在上面找一块尽可能大的矩形来张贴海报，求最大的矩形面积。
输入格式
第二行有 n个整数，分别表示每个建筑物高度hi 。
输出格式
一个整数，表示海报的最大面积。
样例
样例输入
6
5 8 4 4 8 4
样例输出
24
思路
-
建立一个单调递增栈，所有元素各进栈和出栈一次即可。每个元素出栈的时候更新最大的矩形面积。
-
对于栈内的元素，要保证其前面的元素的高度低于此元素，这样才能对前面的元素进行延续处理，否则就将其弹出，因为前面的元素的状态无法再继续扩展，只能以下一个元素为基础进行继承
过程模拟：
-
设栈内的元素为一个二元组（x, y），x表示矩形的高度，y表示矩形的宽度。
-
若原始矩形高度分别为2,1,4,5,1,3,3
-
高度为2的元素进栈，当前栈为（2，1）
-
高度为1的元素准备进栈，但必须从栈顶开始删除高度大于或等于1的矩形，因为2已经不可能延续到当前矩形。删除（2，1）这个元素之后，更新最大矩形面积为2*1=2，然后把它的宽度1累加到当前高度为1的准备进栈的矩形，然后进栈，当前栈为（1，2）
-
高度为4的元素进栈，当前栈为（1，2） （4，1）
-
高度为5的元素进栈，当前栈为（1，2） （4，1） （5，1）
-
高度为1的元素准备进栈，删除（5，1）这个元素，更新最大矩形面积为5·1=5，把1累加到下一个元素，得到（4，2），删除（4，2），更新最大矩形面积为4·2=8，把2累加到下一个元素，得到（1，4），1*4=4<8，不必更新，删除（1，4），把4累加到当前准备进栈的元素然后进栈，当前栈为（1，5）
-
高度为3的元素进栈，当前栈为（1，5） （3，1）
-
高度为3的元素准备进栈，删除（3，1），不必更新，把1累加到当前准备进栈的元素然后进栈，当前栈为（1，5） （3，2）
-
把余下的元素逐个出栈，（3，2）出栈，不必更新，把2累加到下一个元素，当前栈为（1，7），（1，7）出栈，不必更新。栈空，结束。
-
最后的答案就是8。
-
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 4e5+10; 7 8 long long ans; 9 int hei,tmp,tot,top; 10 struct ret{ 11 int h; 12 int d; 13 }stack[maxn];//模拟栈 14 15 int main(){ 16 freopen("post.in","r",stdin); 17 freopen("post.out","w",stdout); 18 int n;scanf("%d",&n); 19 for(int i = 1;i <= n;i++){ 20 tmp = 0; 21 scanf("%d",&hei); 22 while(top > 0 && stack[top-1].h >= hei){//弹出比它大的元素 23 tot = stack[top-1].h * (stack[top-1].d + tmp); 24 if(tot > ans)ans = tot; 25 tmp += stack[top-1].d;//宽度可以继承 26 top--; 27 } 28 stack[top].h = hei; 29 stack[top].d = 1+tmp;//若前方为弹出，则宽度为1 30 top++; 31 } 32 tmp = 0; 33 while(top>0){//清空栈内元素 34 tot = stack[top - 1].h * (stack[top-1].d+tmp); 35 if(tot > ans)ans = tot; 36 tmp += stack[top-1].d; 37 top--; 38 } 39 printf("%lld",ans); 40 return 0; 41 42 }