leetcode栈

84. 柱状图中最大的矩形

枚举每一个柱子，将其高度设置为最大矩形的高度。
然后从这根柱子出发，往两边找到第一个比它矮的柱子，那么这两根柱子就是最大矩形的边界。
时间复杂度On2，空间复杂度O1

class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            int height = heights[i];
            int left = i, right = i;
            while (left >= 0 && heights[left] >= height) {
                left--;
            }
            while (right < heights.length && heights[right] >= height) {
                right++;
            }
            res = Math.max(res, height * (right - left - 1));
        }
        return res;
    }
}

优化：

使用单调栈快速确定每一根柱子的左右边界。

单调递增栈的特性：
栈内元素保持单调递增，进栈时，如果新的元素比栈顶元素大，则直接进栈。如果新的元素比栈顶元素小，则不断出栈，直至栈顶元素比新的元素小，然后再进栈。
当某个元素出栈时，新栈顶的元素一定是前一个比它小的元素，待入栈的元素一定是后一个比它小的元素。

在数组左右插入一根高为0的柱子，使代码更简洁，不用考虑出栈的时候栈为空的情况，也不用考虑遍历完成之后，栈中还有元素的情况。

时间复杂度On,空间复杂度On

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        int len = heights.length + 2;
        newHeights[0] = newHeights[len - 1] = 0;
        //src源数组,srcPos复制开始位置,dest目标数组,destPos目标数组开始位置,length复制的长度
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int res = 0;
        for (int i = 1; i < len; i++) {
            while (newHeights[stack.peek()] > newHeights[i]) {
                int curHeight = newHeights[stack.poll()];
                int width = i - stack.peek() - 1;
                res = Math.max(res, curHeight * width);
            }
            stack.push(i);
        }
        return res;
    }
}

85. 最大矩形

可以转化为84题，只需要求出每一层的 heights[] 然后传给上一题的函数。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for (int row = 0; row < matrix.length; row++) {
            //遍历每一列，更新高度
            for (int col = 0; col < matrix[0].length; col++) {
                if (matrix[row][col] == '1') {
                    heights[col] += 1;
                } else {
                    heights[col] = 0;
                }
            }
            //调用上一题的解法，更新函数
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }
    
    public int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        int len = heights.length + 2;
        newHeights[0] = newHeights[len - 1] = 0;
        //src源数组,srcPos复制开始位置,dest目标数组,destPos目标数组开始位置,length复制的长度
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int res = 0;
        for (int i = 1; i < len; i++) {
            while (newHeights[stack.peek()] > newHeights[i]) {
                int curHeight = newHeights[stack.poll()];
                int width = i - stack.peek() - 1;
                res = Math.max(res, curHeight * width);
            }
            stack.push(i);
        }
        return res;
    }
}