Force buckle monotone stack

Monotonic stack

The maximum rectangular area of the histogram

Ideas
Find the maximum rectangular area , You can get the positions of the left and right columns that are less than the current column height , Take the distance between the two boundary columns as the width , The current column is the height, and the maximum area of the lowest column with the current column is obtained .

Use a stack to store monotonically increasing data subscripts , When a decreasing value is encountered, the stack calculation area operation is performed .

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 The largest rectangle

Ideas
Each layer can be regarded as a histogram from top to bottom , Solve the maximum rectangular area of the histogram by monotone stack .

class Solution {
    
    public int maximalRectangle(char[][] matrix) {
    
        /*  For each row, calculate the continuous 1 The number of ,  Then apply it   The same algorithm of the maximum histogram solves the maximum area （ Monotonic stack ） */
        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++) {
    
                //  Find the continuity above each grid 1 Number （ Include this case ）
                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;
    }
}