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.
1 public class Solution { 2 public int largestRectangleArea(int[] height) { 3 if (height.length==0) return 0; 4 5 Stack<Integer> index = new Stack<Integer>(); 6 index.push(-1); 7 int max = 0; 8 for (int i=0;i<height.length;i++){ 9 while (index.peek()!=-1){ 10 if (height[index.peek()]>height[i]){ 11 int cur = index.pop(); 12 max = Math.max(max,height[cur]*(i-index.peek()-1)); 13 } else break; 14 } 15 index.push(i); 16 } 17 18 while (index.peek()!=-1){ 19 int cur = index.pop(); 20 max = Math.max(max,height[cur]*(height.length-index.peek()-1)); 21 } 22 23 return max; 24 } 25 26 }
Leetcode-Largest Rectangle in Histogram
原文：http://www.cnblogs.com/lishiblog/p/4166268.html