84. 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.

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.

思路: 这道题目从左边开始找，去找最大的长方形面积；
1.首先什么时候计算长方形面积？
2.如何确定长方形的长，宽跟高？
我们这样来想，如果每次找到的元素都比之前元素的值要大，就说明之前的长方形包含在新加入的元素组成的长方形里面；原来的长方形被extend了，而这个过程是个单调递增过程。 如果找到元素比之前元素小，那么说明之前的长方形不能extend了（这时候我们也找到了右边界），也就需要计算之前长方形的面积；如果确定左边界呢？ 我们可以用stack把之前的点的坐标都保存起来，而放入stack中的条件就是当前元素的值要大于栈顶元素的值，这样才能保证你的长方形是一直extend的。 当当前元素的值比stack栈顶元素值小的时候，确定右边界为当前元素坐标， 而左边界, 跟长方形的高则需要不停的pop stack中的元素来获得； 计算长方形面积are = h*(right – left)，并跟一个全局变量max进行比较。 注意当遍历到最后一个元素的时候，右边界也就是数组的长度， 我们要不停的pop出stack中的元素获得左边界并计算， 当stack为空的时候，不要忘记左边界可以获得0， 计算整个数组长度为宽构成的长方形面积。

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) 
            return 0;
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= heights.length; i++) {
            int curVal = i == heights.length ? 0 : heights[i];
            while(!stack.isEmpty() && curVal <= heights[stack.peek()]) { // 当前index元素的height小于等于栈顶元素的height, 即找到了右边界, 需要连续pop stack来获得左边界并进行计算.
                int h = heights[stack.pop()];
                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                int right = i;
                int area = h * (right - left);
                max = Math.max(area, max);
            }
            stack.push(i); 
        }
        return max;    
    }
}