一张半边参差不齐的网格纸(网格边长均为1),有一边是完整没有破损的。现要从中剪出一片面积最大的矩形纸片。
给定网格纸中完整边的长度N(1≤N≤1000000),以及网格中每一列残存部分的高度(1≤高度≤10000),输出能够剪出的最大矩形纸片面积。
例如:N=6,每一列残存部分的高度依次为3、2、1、4、5、2,如下图所示:
可以发现,沿着红色框可以剪出的矩形纸片面积最大,为8,所以输出8。
【输入描述】
第一行输入一个正整数N(1≤N≤1000000),表示纸片完整边的长度
第二行输入N个正整数(1≤正整数≤10000),表示每列格子残存部分的高度,两个正整数之间用一个空格隔开
【输出描述】
输出一个正整数,表示能够剪出的最大矩形纸片面积
【样例输入】
6
3 2 1 4 5 2
【样例输出】
8
#include<iostream> #include<cstdio> using namespace std; int n; int a[1000006],ans;//a[i]保存了第i列的高度 int st[1000006],top,t;//st为单调递增栈,保存高度递增的柱子编号 int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i); for(int i=1;i<=n;i++) { if(a[i]>a[st[top]])//如果当前柱子高度比栈顶柱子高,则列编号进栈 st[++top]=i; else { //当栈不空且栈顶柱子高于当前柱子时,弹出栈顶元素 while(top>0&&a[st[top]]>=a[i]) { t=st[top--]; ans=max(ans,(i-st[top]-1)*a[t]);//更新最大高度 } //当前列编号进栈 st[++top]=i; } } //遍历完序列后,弹出栈内剩余柱子 //栈内剩余柱子的右边界默认为序列的最大长度 while(top>0) { t=st[top--]; ans=max(ans,(n-st[top])*a[t]); } cout<<ans; return 0; }