首页 > 代码库 > 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.
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]
,
return10
.
方法
本题没有做出来,是参考http://blog.csdn.net/doc_sgl/article/details/11805519。
public int largestRectangleArea(int[] height) { if (height == null || height.length == 0) { return 0; } int len = height.length; int[] newHeight = new int[len + 1]; for (int i = 0; i < len; i++) { newHeight[i] = height[i]; } newHeight[len] = 0; Stack<Integer> stack = new Stack<Integer>(); int i = 0; int max = 0; while(i < newHeight.length) { if (stack.isEmpty() || newHeight[stack.peek()] <= newHeight[i]) { stack.push(i); i++; } else { while (!stack.isEmpty() && newHeight[stack.peek()] > newHeight[i]) { int h = newHeight[stack.peek()]; stack.pop(); int wide; if (stack.isEmpty()) { wide = i; } else { wide = i - stack.peek() - 1; } int tempMax = h * wide; if (max < tempMax) { max = tempMax; } } stack.push(i); i++; } } return max; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。