【LEETCODE】模拟面试-84-Largest Rectan

题目：

https://leetcode.com/problems/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.

Java

public class Solution {

    public int largestRectangleArea(int[] heights){
    
        if ( heights == null || heights.length == 0 )
            return 0;
        
        Deque<Integer> stack = new LinkedList<Integer>();   //store index
        int max = 0;
        
        for ( int i = 0; i <= heights.length; i++ ){
            
            int curVal = (i == heights.length) ? 0 : heights[i];                //如果i到array的外面了，curVal＝0，否则就为当前index装的高度
            
            while ( !stack.isEmpty() && heights[stack.peekLast()] >= curVal ){      //curVal 小于heights[stack.peekLast()]，说明cur是最顶端一点的右边界
                                                                                    //如果 curVal 大于stack.peekLast()，说明这是cur的一个左边界
                                                                                    //stack里每个元素都是后一个元素的左边界，停止add的时候说明碰到了右边界
                int height = heights[stack.pollLast()];                             //pollLast get height(index) AND REMOVE index from stack
                int leftBound = stack.isEmpty() ? 0 : (stack.peekLast() + 1);       //注意 why +1: since pollLast() removed
                int rightBound = i;
                max = Math.max( max, height * (rightBound - leftBound) );           //用公式计算面积
            }       

            stack.addLast(i);                           //stack=[1,4]时，说明 1处比4处值小，但是2处被弹出去了，说明4处曾经是2处的右边界，4处相当于凹心
            
        }
        
        
        return max;
    }
}