LeetCode84.柱状图中最大的矩形

题目链接：LeetCode84

题解

单调栈板子题，创建一个单调递增栈（栈底到栈顶是递增的），栈内存放的数组下标，遍历数组，将下标存进栈内，以样例来说

首先栈空，0直接进栈；然后因为nums[stack.peek()] > nums[1]，所以0出栈了，同时记录以num[0]为高的矩形的面积，当前遍历到的数组下标为i，此时i是1，k等于0出站后，栈顶元素的下标,k= stack.isEmpty() ? -1 : stack.peek()，最终，底的长度就是i-k-1。

如果数组已经遍历到结束了，栈内还有值，就需要将他们依次弹出，此时的i=nums.length()，k=stack.isEmpty() ? -1 : stack.peek()。

整个流程用一个maxArea变量维护，找到最大值即可

代码

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