Maximal Rectangle

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

Solution:

  1. public class Solution {
  2.   public int maximalRectangle(char[][] M) {
  3.     if (M == null || M.length == 0 || M[0].length == 0) {
  4.       return 0;
  5.     }
  7.     int max = 0;
  8.     int m = M.length;
  9.     int n = M[0].length;
  11.     int[][] H = new int[m][n];
  13.     for (int i = 0; i < m; i++) {
  14.       for (int j = 0; j < n; j++) {
  15.         int v = getInt(M[i][j]);
  17.         if (i == 0 || v == 0) {
  18.           H[i][j] = v;
  19.         } else {
  20.           H[i][j] = v + H[i - 1][j];
  21.         }
  22.       }
  24.       int res = largestRectangleArea(H[i]);
  26.       max = Math.max(max, res);
  27.     }
  29.     return max;
  30.   }
  32.   public int largestRectangleArea(int[] A) {
  33.     if (A == null) {
  34.       return 0;
  35.     }
  37.     Stack<Integer> stack = new Stack<Integer>();
  39.     int n = A.length, max = 0;
  41.     for (int i = 0; i < n; i++) {
  42.       while (!stack.isEmpty() && A[i] <= A[stack.peek()]) {
  43.         int index = stack.pop();
  44.         int left = stack.isEmpty() ? 0 : stack.peek() + 1;
  46.         max = Math.max(max, A[index] * (i - left));
  47.       }
  49.       stack.push(i);
  50.     }
  52.     while (!stack.isEmpty()) {
  53.       int index = stack.pop();
  54.       int left = stack.isEmpty() ? 0 : stack.peek() + 1;
  56.       max = Math.max(max, A[index] * (n - left));
  57.     }
  59.     return max;
  60.   }
  62.   private int getInt(char ch) {
  63.     return (int)(ch - '0');
  64.   }
  65. }