原题链接在这里：

题目：

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.

题解： 

用stack保存数组的index, 确保stack中index对应的高度是递增的.

当出现较小高度时需要不停的pop出比它大的index, 更新最大面积. 

如何更新呢. 高度是heights[stk.pop()], 宽度是stk pop后的顶部index, stk.peek()到i之间的距离-1.

最后在从后到前更新次最大面积.

Time Complexity: O(n). n = heights.length. 

Space: O(n).

AC Java:

1 class Solution { 2     public int largestRectangleArea(int[] heights) { 3         if(heights == null || heights.length == 0){ 4             return 0; 5         } 6          7         int res = 0; 8         Stack
     
       stk = new Stack
      
       (); 9         stk.push(-1);10         11         for(int i = 0; i
       
        =heights[i]){13                 int h = heights[stk.pop()];14                 res = Math.max(res, h*(i-stk.peek()-1));        15             }16             17             stk.push(i);18         }19         20         while(stk.peek()!=-1){21             res = Math.max(res, heights[stk.pop()]*(heights.length-stk.peek()-1));22         }23                            24         return res;        25     }26 }