51nod 1102单调栈

本文主要是介绍51nod 1102单调栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1102 面积最大的矩形

基准时间限制：1 秒 空间限制：131072 KB 分值: 20  难度：3级算法题

 收藏

 关注

有一个正整数的数组，化为直方图，求此直方图包含的最大矩形面积。例如 2,1,5,6,2,3，对应的直方图如下：

面积最大的矩形为5,6组成的宽度为2的矩形，面积为10。

第1行：1个数N，表示数组的长度(0 <= N <= 50000)
第2 - N + 1行：数组元素A[i]。(1 <= A[i] <= 10^9)

输出最大的矩形面积

6
2
1
5
6
2
3

10

很明确的做法是对于每一个矩形，向左右延伸至无法延伸然后计算更新最大值，朴素作法确实费时；
我们维护一个高度递增的单调栈，如果当前a[i]比栈顶元素的高/相等就一直push，直到遇见高度小于栈顶元素高度时候，说明前面部分矩形的右端点最大只能到这了，因为高度不够了，
接着我们就不断的提出栈顶元素，将他作为左端点，第一个出栈顶元素作为右端点更新最大值，直到栈空了或者栈顶元素不再>=a[i],退出pop操作。
然后将ai加入栈顶，注意宽度是1+所有出栈元素宽度和，因为前面小于这些元素高度的矩形还是能穿过他们的。

struct node
{int h,w;
};
int n,a;
stack<node>s;
int main()
{ios::sync_with_stdio(false);cin>>n;ll ans=0;for(int i=0;i<n;i++){cin>>a;if(s.empty() || s.top().h<=a) s.push(node{a,1});else{int w=0;while(!s.empty() && s.top().h>a){w+=s.top().w;ans=max(ans,(ll)s.top().h*w);s.pop();}s.push(node{a,w+1});}}int w=0;while(!s.empty()){w+=s.top().w;ans=max(ans,(ll)s.top().h*w);s.pop();}cout<<ans<<endl;return 0;
}

这篇关于51nod 1102单调栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！