Largest Rectangle in Histogram

给一个数组, 里面的数组代表一个柱状图, 每个数代表高度. 求最大的矩阵. 这个题用一个stack来track当前最高的柱子, 这样我们知道长度(当前的i)和高度(stack里增序的柱子)的面积. 这个面积就是答案.

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0)
            return 0;
        Stack<Integer> st = new Stack<Integer>();
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i <= heights.length; i++) {
            int cur = i==heights.length? 0 : heights[i];
            while(!st.isEmpty() && cur <= heights[st.peek()]){
                int h = heights[st.pop()];
                int w = st.isEmpty() ? i : i - st.peek() - 1;
                max = Math.max(max, h*w);
            }   
            st.push(i);
        }
        return max;
    }
}