Question

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

Example:

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

Thinking:

  • Method 1: Use the method of Monostack as question 84: 84. Largest Rectangle in Histogram
    • we use a height array to save the historgram.
    • if current value is 1, we increase the value saved in that index.
    • if current value is 0, we set the value to 0. 
      class Solution {
  public int maximalRectangle(char[][] matrix) {
  if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
  int res = 0;
  int[] height = new int[matrix[0].length + 1];
  for(int row = 0; row < matrix.length; row++){
      for(int i = 0; i < matrix[0].length; i++){
          if(matrix[row][i] == '1') height[i]++;
          else height[i] = 0;
      }
      Stack<Integer> stack = new Stack<>();
      for(int j = 0; j <= matrix[0].length; j++){
          while(!stack.isEmpty() && height[j] < height[stack.peek()]){
              int h = height[stack.pop()];
              int index = stack.isEmpty() ? -1: stack.peek();
              res = Math.max(res, h * (j - index - 1));
          }
          stack.push(j);
      }
  }
  return res;
  }
}
  • Method 2: dp
    • we define 3 arrays for each row:
      • left(save the first index of 1 in current row, still need to compare with previous value), initial value is 0.
      • right(save the last index of 1 in current row, need to compare with previous value), initialized with len.
      • height(record the height as historgram)
      • area = height * (right - left) ```Java /** Example: 0 1 2 3 4 row0 [“1”,”0”,”1”,”0”,”0”], row1 [“1”,”0”,”1”,”1”,”1”], row2 [“1”,”1”,”1”,”1”,”1”], row3 [“1”,”0”,”0”,”1”,”0”]

height[]: height array saves the historgram for current row. row0 [1,0,1,0,0], row1 [2,0,2,1,1], row2 [3,1,3,2,2], row3 [4,0,0,3,0]

left[]: left array saves the first index in current row and we need to compare it with the previous row left array. row0 [0,0,2,0,0], row1 [0,0,2,2,2], row2 [0,0,2,2,2], row3 [0,0,0,3,0]

right[]: right array saves the last index in current row(need to compare it with the previous row right array.) row0 [1,5,3,5,5], row1 [1,5,3,5,5], row2 [1,5,3,5,5], row3 [1,5,5,4,5] */ class Solution { public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int res = 0, len = matrix[0].length; int[] left = new int[len]; int[] right = new int[len]; int[] height = new int[len]; for(int i = 0; i < len; i++) right[i] = len; for(int row = 0; row < matrix.length; row++){ int cur_left = 0, cur_right = len; for(int i = 0; i < len; i++){ if(matrix[row][i] == ‘0’) height[i] = 0; else height[i]++; } for(int i = 0; i < len; i++){ if(matrix[row][i] == ‘1’){ left[i] = Math.max(left[i], cur_left); }else{ cur_left = i + 1; left[i] = 0; } } for(int i = len - 1; i >= 0; i–){ if(matrix[row][i] == ‘1’){ right[i] = Math.min(right[i], cur_right); }else{ cur_right = i; right[i] = len; } } for(int i = 0; i < len; i++){ res = Math.max(res, height[i] * (right[i] - left[i])); } } return res; } } ```

Reference

  1. Leetcode : 85. Maximal Rectangle 讲解