85. Maximal Rectangle

 一刷 07/2022

Version #1 Stack

关键是求maximum rectangle in histogram

Time O(MN)

Space O(N)

Runtime: 34 ms, faster than 67.15% of Java online submissions for Maximal Rectangle.

Memory Usage: 54.6 MB, less than 54.71% of Java online submissions for Maximal Rectangle.

class Solution {

    public int maximalRectangle(char[][] matrix) {

        int[] row = new int[matrix[0].length];

        int max = 0;

        for (int y = 0; y < matrix.length; y++) {

            for (int x = 0; x < matrix[0].length; x++) {

                if (matrix[y][x] == '0') {

                    row[x] = 0;

                } else {

                    row[x]++;

                }

            }

            max = Math.max(max, maxRecInHisto(row));

        }

        return max;

    }

    

    private int maxRecInHisto(int[] row) {

        int max = 0;

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < row.length; i++) {

            while (!stack.isEmpty() && row[stack.peek()] >= row[i]) {

                int h = row[stack.pop()];

                int w = i - (stack.isEmpty() ? -1 : stack.peek()) - 1;

                max = Math.max(max, h * w);

            }

            stack.push(i);

        }

        int i = row.length;

        while (!stack.isEmpty()) {

            int h = row[stack.pop()];

            int w = i - (stack.isEmpty() ? -1 : stack.peek()) - 1;

            max = Math.max(max, h * w);

        }

        return max;

    }

}