0085. Maximal Rectangle

https://leetcode.com/problems/maximal-rectangle

Description

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

**Input:** matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
**Output:** 6
**Explanation:** The maximal rectangle is shown in the above picture.

Example 2:

**Input:** matrix = []
**Output:** 0

Example 3:

**Input:** matrix = [["0"]]
**Output:** 0

Example 4:

**Input:** matrix = [["1"]]
**Output:** 1

Example 5:

**Input:** matrix = [["0","0"]]
**Output:** 0

Constraints:

• rows == matrix.length

• cols == matrix[i].length

• 0 <= row, cols <= 200

• matrix[i][j] is '0' or '1'.

ac1: Stack

similar with #84

class Solution {
    public int maximalRectangle(char[][] matrix) {
        // edge cases
        if (matrix.length == 0 || matrix[0].length == 0) return 0;

        int max = 0;
        int row = matrix.length, col = matrix[0].length;
        int[] h = new int[col];
        // iterate row
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                h[c] = matrix[r][c] == '1' ? h[c] + 1 : 0;
            }
            max = Math.max(max, maxArea(h)); // O(n)
        }

        return max;
    }
    private int maxArea(int[] h) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(-1);
        int max = 0;
        for (int i = 0; i <= h.length; i++) {
            int currh = i == h.length ? 0 : h[i];
            while (stack.peek() != -1 && currh < h[stack.peek()]) {
                max = Math.max(max, h[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return max;
    }
}
/*
stack, similar with #84
row by row: int[] h = new int[matrix[0].length]
    if [i] == 1, h[i] = h[i] + 1, otherwise h[i] = 0
    calculate max area like #84
*/