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;
    }
}