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. class Solution {
  4. public:
  5.     int maximalRectangle(vector<vector<char> > &matrix) {
  6.         if (matrix.empty())  return 0;
  8.         const int m = matrix.size();
  9.         const int n = matrix[0].size();
  10.         vector<int> H(n, 0);
  11.         vector<int> L(n, 0);
  12.         vector<int> R(n, 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] = 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] = min(R[j], right);
  31.                     ret = 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/cpp/dp/maximal-rectangle.html