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

DP。用f[i][j]来记录i行以j列为结尾，往前连续的1的个数。然后再一个O(n^3)的循环来找以(i, j)为右下角的矩形最大的1的面积。

 1 class Solution {
 2 private:
 3     int f[1000][1000];
 4 public:
 5     int maximalRectangle(vector<vector<char> > &matrix) {
 6         // Start typing your C/C++ solution below
 7         // DO NOT write int main() function
 8         for(int i = 0; i < matrix.size(); i++)
 9             f[i][0] = matrix[i][0] == '1' ? 1 : 0;
10             
11         for(int i = 0; i < matrix.size(); i++)
12             for(int j = 1; j < matrix[i].size(); j++)
13                 f[i][j] = matrix[i][j] == '1' ? f[i][j-1] + 1 : 0;
14                 
15         int ret = 0;
16         
17         for(int i = 0; i < matrix.size(); i++)
18             for(int j = 0; j < matrix[i].size(); j++)
19             {
20                 int k = i;
21                 int width = INT_MAX;
22                 
23                 while(k >= 0)
24                 {
25                     if (f[k][j] == 0)
26                         break;
27                     
28                     width = min(width, f[k][j]);
29                 
30                     ret = max(ret, width * (i - k + 1));   
31                     
32                     k--;                   
33                 }
34             }
35             
36         return ret;
37     }
38 };

O(n^2)的算法，可以把问题看成求多个直方图的最大矩形面积，这样就可以从上往下来做例如第i层就是0~i的直方图，第i+1就是0~i+1的直方图，这样求直方图的复杂度O(n)，于是就有O(n^2)

 1 class Solution {
 2 public:
 3     int calArea(vector<int> &a, vector<int> &width)
 4     {
 5         for(int i = 0; i < width.size(); i++)
 6             width[i] = 0;
 7             
 8         stack<int> s;
 9         for(int i = 0; i < a.size(); i++)
10             if (s.empty())
11             {
12                 s.push(i);
13                 width[i] = 0;
14             }
15             else
16             {
17                 while(!s.empty())
18                 {
19                     if (a[s.top()] < a[i])
20                     {
21                         width[i] = i - s.top() - 1;
22                         s.push(i);
23                         break;
24                     }
25                     else
26                         s.pop();
27                 }
28                 
29                 if (s.empty())
30                 {
31                     s.push(i);
32                     width[i] = i;
33                 }
34             }
35             
36         while(!s.empty())
37             s.pop();
38             
39         for(int i = a.size() - 1; i >= 0; i--)
40             if (s.empty())
41             {
42                 s.push(i);
43                 width[i] = 0;
44             }
45             else
46             {
47                 while(!s.empty())
48                 {
49                     if (a[i] > a[s.top()])
50                     {
51                         width[i] += s.top() - i - 1;
52                         s.push(i);
53                         break;
54                     }
55                     else
56                         s.pop();
57                 }
58                 
59                 if (s.empty())
60                 {
61                     width[i] += a.size() - i - 1;
62                     s.push(i);
63                 }
64             }
65         
66         int maxArea = 0;    
67         for(int i = 0; i < width.size(); i++)
68             maxArea = max(maxArea, (width[i] + 1) * a[i]);
69             
70         return maxArea;
71     }
72     
73     int maximalRectangle(vector<vector<char> > &matrix) {
74         // Start typing your C/C++ solution below
75         // DO NOT write int main() function
76         if (matrix.size() == 0)
77             return 0;
78             
79         vector<int> a(matrix[0].size(), 0);
80         vector<int> width(matrix[0].size());
81         
82         int maxArea = 0;
83         for(int i = 0; i < matrix.size(); i++)
84         {
85             for(int j = 0; j < matrix[i].size(); j++)
86                 a[j] = matrix[i][j] == '1' ? a[j] + 1 : 0;
87                 
88             maxArea = max(maxArea, calArea(a, width));
89         }
90         
91         return maxArea;
92     }
93 };