Maximal Rectangle

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

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Solution:

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;
        if (n == 0) return 0;
        int[][] M = new int[m][n];
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                M[i][j] = matrix[i][j] - '0';
            }
        }
        for (int i = 1; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                M[i][j] = M[i][j] == 0 ? 0 : 1 + M[i - 1][j];
            }
        }
        int max = 0;
        for (int i = 0; i < m; i ++) {
            max = Math.max(max, maxHistogram(M[i]));
        }
        return max;
    }
    
    // 3 1 3 2 2
    private int maxHistogram(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int max = 0;
        for (int i = 1; i <= arr.length; i ++) {
            int cur = i == arr.length ? -1 : arr[i];
            if (stack.isEmpty() || cur >= arr[stack.peekFirst()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && cur < arr[stack.peekFirst()]) {
                    int height = arr[stack.pop()];
                    int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
                    max = Math.max(max, height * (i - left));
                }
                stack.push(i);
            }
        }
        return max;
    }
}