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.

分析

无

代码

  1. // Maximal Rectangle
  2. // 时间复杂度O(n^2)，空间复杂度O(n)
  3. public class Solution {
  4.     public int maximalRectangle(char[][] matrix) {
  5.         if (matrix.length == 0)  return 0;
  7.         final int m = matrix.length;
  8.         final int n = matrix[0].length;
  9.         int[] H = new int[n];
  10.         int[] L = new int[n];
  11.         int[] R = new int[n];
  12.         Arrays.fill(R, n);
  14.         int ret = 0;
  15.         for (int i = 0; i < m; ++i) {
  16.             int left = 0, right = n;
  17.             // calculate L(i, j) from left to right
  18.             for (int j = 0; j < n; ++j) {
  19.                 if (matrix[i][j] == '1') {
  20.                     ++H[j];
  21.                     L[j] = Math.max(L[j], left);
  22.                 } else {
  23.                     left = j+1;
  24.                     H[j] = 0; L[j] = 0; R[j] = n;
  25.                 }
  26.             }
  27.             // calculate R(i, j) from right to left
  28.             for (int j = n-1; j >= 0; --j) {
  29.                 if (matrix[i][j] == '1') {
  30.                     R[j] = Math.min(R[j], right);
  31.                     ret = Math.max(ret, H[j]*(R[j]-L[j]));
  32.                 } else {
  33.                     right = j;
  34.                 }
  35.             }
  36.         }
  37.         return ret;
  38.     }
  39. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dp/maximal-rectangle.html