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.
Solution:
http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
这个大哥讲得太清楚了！！120个赞啊！！！
1 public class Solution { 2 public int largestRectangleArea(int[] height) { 3 if(height==null) 4 return 0; 5 int[] h=new int[height.length+1]; 6 h=Arrays.copyOf(height, height.length+1); 7 Stack<Integer> stack=new Stack<Integer>(); 8 int i=0; 9 int maxArea=0; 10 while(i<h.length){ 11 if(stack.size()==0||h[stack.peek()]<=h[i]){ 12 stack.push(i++); 13 }else{ 14 int t=stack.pop(); 15 maxArea=Math.max(maxArea, h[t]*(stack.isEmpty()?i:i-stack.peek()-1)); 16 } 17 } 18 return maxArea; 19 } 20 }
[Leetcode] Largest Rectangle in Histogram
原文：http://www.cnblogs.com/Phoebe815/p/4116696.html