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

思路：

动态规划：

f[i][j] 表示在第i行中以(i,j)点结束点的前面有多少个连续的1,就是用f[i][j]来记录i行以j列为结尾，往前连续的1的个数。

然后用O(n^3)的循环来找以(i, j)为右下角的矩形最大的矩形的面积。

例如数组为

0 0 1

1 1 1

0 1 1

那么f数组为

0 0 1

1 2 3

0 1 2

在计算f[i][j]时使用的是一维动态规划

计算(i, j)为右下角的矩形最大的矩形的面积时，就是就去第0行到i行中以j结尾矩形的最大值，就是之前求过的 Largest Rectangle in Histogram

相当于是每一列，求一次Largest Rectangle in Histogram，然后求其所有列的最大值。。

方法一： O（n^3）

转载 http://www.cnblogs.com/remlostime/archive/2012/11/12/2766566.html

 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             for(int i = 0; i < matrix.size(); i++)
17             {
18                 for(int j = 0; j < matrix[i].size(); j++)
19                 {
20                     int wid = INT_MAX;
21                     for(int k = i; k >=0; k--)
22                     {
23                         if(f[i][j] == 0)
24                             break;
25                         wid = min(wid, f[k][j]);
26                         ret = max(ret, wid* (i-k +1));
27                     }
28 
29                 }
30             }
31             return ret;
32 
33         }
34 };

方法二，基于largestRectangleArea

将matrxi看出n行，求出每行的高度，然后调用largestRectangleArea

求解每行的高度的时候，使用的动态规划方法和方法一类似，

f[i][j]表示第i列中以（i，j）为结束连续1的个数

重点是

if(matrix[i][j] == '1')
f[i][j] = f[i-1][j] + 1;
else
f[i][j] = 0;

共n行，每行调用largestRectangleArea的复杂度为O(n)，所以是O（n^2）,空间复杂度由于有矩阵f的存在，也是O（n^2）

 1 class Solution
 2 {
 3     public:
 4         int largestRectangleArea(vector<int> &height) {
 5 
 6             //add 0 to the end
 7             height.push_back(0);
 8 
 9             int size = height.size(); //this new_size is 1 + old_size
10             stack<int> st;
11 
12             int max_area = 0;
13 
14 
15 
16             for(int i = 0; i< size; )
17             {
18                 if(st.empty() || height[i] > height[st.top()])
19                 {
20                     st.push(i);
21                     i++;
22                 }
23                 else
24                 {
25                     //st must be not empty here
26                     // i can't ++; handle many times perhaps
27 
28                     int idx = st.top();
29                     st.pop();
30 
31                     int area;
32 
33                     if(st.empty())
34                     {
35                         area = height[idx] * i;
36                     }
37                     else
38                     {
39                         area = height[idx] * (i-st.top()-1);
40                     }
41 
42                     max_area = max(max_area, area);
43 
44                 }
45             }
46             return max_area;
47         }
48 
49         int maximalRectangle(vector<vector<char> > &matrix)
50         {
51             if(matrix.empty() || matrix[0].empty())
52                 return 0;
53             size_t row = matrix.size();
54             size_t col = matrix[0].size();
55 
56             //construct matrix f;
57             vector<vector<int> > f(row);
58             vector<int> array;
59             array.resize(col, 0);
60 
61             for(int i = 0; i < row; i++)
62                 f[i] = array;
63 
64             // initial f[0], the first row
65             for(int j = 0; j < col; j++)
66             {
67                 if(matrix[0][j] == '1')
68                     f[0][j] = 1;
69                 else
70                     f[0][j] = 0;
71             }
72 
73             for(int i = 1; i < row; i++)
74             {
75                 for(int j = 0; j < col; j++)
76                 {
77                     if(matrix[i][j] == '1')
78                         f[i][j] = f[i-1][j] + 1;
79                     else
80                         f[i][j] = 0;
81                 }
82             }
83 
84             int ret = 0;
85             for(int i = 0; i < row; i++)
86             {
87 
88                 ret = max(ret, largestRectangleArea(f[i]));
89             }
90 
91             return ret;
92 
93         }
94 } ;

适当的优化：

　　由于f[i][j] = f[i-1][j] + 1;的关系，二期在计算第i行时，第i-1行的数据有用，再之前的数据就没有了，所以我么可以不用保留整个col*row的矩阵，而只用一个数组就够了

　　空间复杂度O（n），时间复杂度还是O（n^2）

 1 class Solution
 2 {
 3     public:
 4         int largestRectangleArea(vector<int> &height) {
 5 
 6             //add 0 to the end
 7             height.push_back(0);
 8 
 9             int size = height.size(); //this new_size is 1 + old_size
10             stack<int> st;
11 
12             int max_area = 0;
13 
14 
15 
16             for(int i = 0; i< size; )
17             {
18                 if(st.empty() || height[i] > height[st.top()])
19                 {
20                     st.push(i);
21                     i++;
22                 }
23                 else
24                 {
25                     //st must be not empty here
26                     // i can't ++; handle many times perhaps
27 
28                     int idx = st.top();
29                     st.pop();
30 
31                     int area;
32 
33                     if(st.empty())
34                     {
35                         area = height[idx] * i;
36                     }
37                     else
38                     {
39                         area = height[idx] * (i-st.top()-1);
40                     }
41 
42                     max_area = max(max_area, area);
43 
44                 }
45             }
46             return max_area;
47         }
48 
49         int maximalRectangle(vector<vector<char> > &matrix)
50         {
51             if(matrix.empty() || matrix[0].empty())
52                 return 0;
53             size_t row = matrix.size();
54             size_t col = matrix[0].size();
55 
56             vector<int> f;
57             f.resize(col, 0);
58 
59             int ret = 0;
60             for(int i = 0; i < row; i++)
61             {
62                 // update f
63                 for(int j = 0; j < col; j++)
64                 {
65                     // the first row 
66                     if(i == 0)
67                     {
68                         if(matrix[0][j] == '1')
69                             f[j] = 1;
70                         else
71                             f[j] = 0;
72                     }
73                     // other rows
74                     else
75                     {
76                         if(matrix[i][j] == '1')
77                             f[j] = f[j] + 1;
78                         else
79                             f[j] = 0;
80                     }
81                 }
82 
83                 ret = max(ret, largestRectangleArea(f));
84             }
85 
86             return ret;
87 
88         }
89 } ;