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 heights = [2,1,5,6,2,3],
return 10.
此题需要注意数组overflow情况，即新创建的数组的最后一个元素一定要为0！代码如下：
public class Solution {
public int largestRectangleArea(int[] heights) {
int max = 0;
if(heights.length==0) return max;
int[] h = new int[heights.length+1];
for(int i=0;i<heights.length;i++){
h[i] = heights[i];
}
Stack<Integer> s =new Stack<Integer>();
for(int i=0;i<h.length;i++){
if(s.isEmpty()||h[s.peek()]<=h[i]){
s.push(i);
}else{
while(!s.isEmpty()&&h[s.peek()]>h[i]){
int top= s.pop();
int area = h[top]*(s.isEmpty()?i:i-s.peek()-1);
max = Math.max(max,area);
}
s.push(i);
}
}
return max;
}
}