力扣-单调栈

单调栈

直方图的最大矩形面积

思路
寻找最大矩形面积，可以获取小于当前柱子高度的左右两个柱子位置，以这两个边界柱子距离为宽，当前柱子为高求得以当前柱子为最低柱子的最大面积。

使用一个栈存储单调递增的数据下标，当遇到递减值时则执行出栈计算面积操作。

class Solution {
    
    public int largestRectangleArea(int[] heights) {
    
        LinkedList<Integer> li = new LinkedList<>();
        int max = 0;
        li.push(-1);
        for (int i = 0; i < heights.length; i++) {
    
            while(li.peek() != -1 && heights[li.peek()] > heights[i]) {
    
                max = Math.max(max, heights[li.pop()] * (i - li.peek() - 1));
            }
            li.push(i);
        }
        while(li.peek() != -1) {
    
            max = Math.max(max, heights[li.pop()] * (heights.length - li.peek() - 1));
        }
        return max;
    }
}

85 最大矩形

思路
可以从上往下以每一层作为底边看做一个直方图，通过单调栈对该直方图求解最大矩形面积。

class Solution {
    
    public int maximalRectangle(char[][] matrix) {
    
        /* 对于每一行计算其上连续1的个数， 然后对其应用 最大直方图的相同算法求解最大面积（单调栈） */
        final int rows = matrix.length;
        final int cols = matrix[0].length;
        int[][] m = new int[rows][cols];
        LinkedList<Integer> s = new LinkedList<>();
        s.push(-1);
        int max = 0;
        for (int r = 0; r < rows; r++) {
    
            for (int c = 0; c < cols; c++) {
    
                // 求出每格子上方连续1个数（包含本格）
                if (matrix[r][c] == '1') {
    
                    m[r][c] = 1;
                }
                if (r != 0 && m[r][c] == 1) {
    
                    m[r][c] += m[r - 1][c];
                }
                while(s.peek() != -1 && m[r][c] < m[r][s.peek()]) {
    
                    max = Math.max(max, m[r][s.pop()] * (c - s.peek() - 1));
                }
                s.push(c);
            } 
            while(s.peek() != -1) {
    
                max = Math.max(max, m[r][s.pop()] * (cols - s.peek() - 1));
            }
        }
        return max;
    }
}