寻找直方图中的最大矩形 Largest Rectangle in Histogram

发布时间:2017-1-17 19:05:09 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"寻找直方图中的最大矩形 Largest Rectangle in Histogram",主要涉及到寻找直方图中的最大矩形 Largest Rectangle in Histogram方面的内容,对于寻找直方图中的最大矩形 Largest Rectangle in Histogram感兴趣的同学可以参考一下。

题目:Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.For example,Given height = [2,1,5,6,2,3],return 10. 思路:矩形的高度瓶颈在于最小的高度。顺序扫描数组元素,同时在栈中维护一个递增的序列。当栈为空或是遇到比栈顶元素大的元素时,则认为瓶颈还未到来,只入栈而不计算;当遇到比栈顶元素小的元素时,则认为到达一个瓶颈,则对瓶颈左侧的矩形进行清算。 当扫描完毕后,再对栈中遗留下的元素进行清算。  该方法的时间复杂度O(N),空间复杂度O(N)。 class Solution { public: int max(int a, int b) { if(a > b) return a; else return b; } int largestRectangleArea(vector<int> &height) { stack<int> s; //注意栈中存的是下标 int len = height.size(); int maxs = 0; int k; for(int i=0; i<len; i++) { if(s.empty() || height[s.top()] <= height[i]) s.push(i); else { while(!s.empty() && height[s.top()] > height[i]) { k = s.top(); s.pop(); if(s.empty()) //注意时刻防止栈为空 maxs = max(maxs, i*height[k]); else maxs = max(maxs, (i-s.top()-1)*height[k]); } s.push(i); } } while(!s.empty()) { k = s.top(); s.pop(); if(s.empty()) //注意时刻防止栈为空 maxs = max(maxs, len*height[k]); else maxs = max(maxs, (len-s.top()-1)*height[k]); } return maxs; } };

上一篇:网络编程之路---4
下一篇:[置顶] iOS 常用第三方库

相关文章

相关评论