Leetcode | 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.

穷举很难。之前做Largest Rectangle in Histogram的时候，看到网上有人说这两道题很类似。于是开始往这方面想。

思路如下：

1. 对于第j列，每一行可以算出从j这个位置开始，连续的'1'的个数。这样在第j列就可以计算得到一个histogram。

2. 然后直接应用Largest Rectangle in Histogram的O(n)算法求最大值；

3. 所有最大值再求最大，就是结果。

 1 class Solution {
 2 public:
 3     int largestRectangleArea(vector<int> &height) {
 4         int n = height.size();
 5         if (n == 0) return 0;
 6         
 7         int max = 0, last, area;
 8         
 9         stack<int> indexes;
10         height.push_back(0);
11         
12         for (int i = 0; i < height.size(); ) {
13             if (indexes.empty() || (height[i]>=height[indexes.top()])) {
14                 indexes.push(i);
15                 i++;
16             } else {
17                 last = height[indexes.top()];
18                 indexes.pop();
19                 area = last * (indexes.empty() ? i : i - indexes.top() - 1);
20                 if (area > max) max = area;
21             }
22         }
23         
24         return max;
25     }
26     int maximalRectangle(vector<vector<char> > &matrix) {
27         int m = matrix.size();
28         if (m == 0) return 0;
29         int n = matrix[0].size();
30         if (n == 0) return 0;
31         
32         vector<int> hist(m, 0);
33         int max = 0, area;
34         
35         for (int j = 0; j < n; ++j) {
36             for (int i = 0; i < m; ++i) {
37                 hist[i] = 0; 
38                 for (int k = j; k < n && matrix[i][k] == '1'; ++k) hist[i]++;  
39             }        
40             area = largestRectangleArea(hist);
41             if (area > max) max = area;
42         }
43         return max;
44     }
45 };

当然这样建histogram的复杂度是O(n*m*n)。

建historgram可以事先建好。动态规划啊，竟然没想到。。。。

 1 class Solution {
 2 public:
 3     int largestRectangleArea(vector<int> &height) {
 4         int n = height.size();
 5         if (n == 0) return 0;
 6         
 7         int max = 0, last, area;
 8         
 9         stack<int> indexes;
10         height.push_back(0);
11         
12         for (int i = 0; i < height.size(); ) {
13             if (indexes.empty() || (height[i]>=height[indexes.top()])) {
14                 indexes.push(i);
15                 i++;
16             } else {
17                 last = height[indexes.top()];
18                 indexes.pop();
19                 area = last * (indexes.empty() ? i : i - indexes.top() - 1);
20                 if (area > max) max = area;
21             }
22         }
23         
24         return max;
25     }
26     int maximalRectangle(vector<vector<char> > &matrix) {
27         int m = matrix.size();
28         if (m == 0) return 0;
29         int n = matrix[0].size();
30         if (n == 0) return 0;
31         
32         vector<vector<int> > hists(n + 1, vector<int>(m, 0));
33        
34         for (int j = n - 1; j >= 0; --j) {
35             for (int i = 0; i < m; ++i) {
36                 if (matrix[i][j] == '0') {
37                     hists[j][i] = 0;
38                 } else {
39                     hists[j][i] = hists[j + 1][i] + 1;
40                 }
41             }        
42         }
43         
44         int max = 0, area;    
45         for (int j = n - 1; j >= 0; --j) {
46             area = largestRectangleArea(hists[j]);
47             if (area > max) max = area;
48         }
49         
50         return max;
51     }
52 };

这样就是O(m*n)了。空间复杂度是O(m*n)。