首页 > 代码库 > [leetcode]Largest Rectangle in Histogram
[leetcode]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.
Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3]
.
The largest rectangle is shown in the shaded area, which has area =10
unit.
For example,
Given height = [2,1,5,6,2,3]
,
return 10
.
基本思想:
最基本的方法是穷举所有可能的左右边界组合,复杂度为O(n^2);
现在考虑如果左边界固定,右边界h[k]>h[k-1],那么右边界为k时的面接一定大于等于右边界为k-1;所以对于连续递增的一段区间,我们可以暂时不考虑其作为右边界的情况。当出现h[k]<h[k-1]时,穷举左边界,找到最大的面积。这对上面穷举法做了剪枝。
更简单的一种方法是:当遇到h[k]<h[k-1]时,回退计算前面比h[k]更高的挡板组成的矩形面积,并更新最大的面积,直到前一个挡板比h[k]小。可以结合代码理解。
代码:
int largestRectangleArea(vector<int> &height) { //c++ if(height.size() == 0) return 0; height.push_back(0); int max = 0; vector<int> stack; for(int i = 0; i < height.size(); i++) { while(stack.size() >0&&height[stack.back()]>height[i]) { int h = height[stack.back()]; stack.pop_back(); int left = stack.size()>0?stack.back():-1; if(h*(i-1-left)>max) max = h*(i-1-left); } stack.push_back(i); } return max; }
[leetcode]Largest Rectangle in Histogram
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。