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.
分析：一般一個題目我首先會想想怎么暴力解決，比如這一題，可以枚舉出所有的矩形，求出其中的面積最大者，那么怎么枚舉呢，如果分別枚舉矩形的寬度和高度，這樣還得枚舉矩形的位置，復雜度至少為O(n^4) (計算復雜度是我們把matrix的行、列長度都泛化為n，下同)，我們可以枚舉矩形左上角的位置，那么知道了矩形左上角的位置，怎么計算以某一點為左上角的矩形的最大面積呢？舉例如下，下面的矩陣我們以(0,0)為矩形的左上角：
1 1 1 1 0 0
1 1 1 0 1 1
1 0 1 0 1 1
0 1 1 1 1 1
1 1 1 1 1 1
矩形高度是1時，寬度為第一行中從第一個位置起連續的1的個數，為4，面積為4 * 1 = 4
矩形高度是2時，第二行從第一個位置起連續1的個數是3，寬度為min(3,4) = 3，面積為3*2 = 6
矩形高度為3時，第三行從第一個位置起連續1的個數是1，寬度為min(1,3) = 1，面積為1*3 = 3
矩形高度為4時，第四行從第一個位置起連續1的個數是0，寬度為min(0,1) = 0，面積為0*4 = 0
后面的行就不用計算了，因為上一行計算的寬度是0，下面所有寬度都是0
因此以(0,0)為左上角的矩形的最大面積是6，計算以某一點為左上角的矩形的最大面積復雜度是O(n)。
注意到上面我們用到了信息“從某一行某個位置開始連續的1的個數”，這個我們可以通過動態規劃求得：設dp[i][j]是從點(i,j)開始，這一行連續1的個數，動態規劃方程如下：???????????????????????????????????????????????????????????????? 本文地址
- 初始條件：dp[i][column-1] = (matrix[i][column-1] == '1') （column是matrix的列數）
- dp[i][j] = (matrix[i][j] == '1') ?? 1 + dp[i][j + 1] : 0 ，(從方程看出我們應該從每一行的后往前計算)
計算dp復雜度O(n^2)，枚舉左上角位置以及計算以該位置為左上角的矩形最大面積復雜度是O(n^2*n)=O(n^3)，總的復雜度是O(n^3)
這個算法還可以優化，枚舉到某個點時我們可以假設該點右下方全是1，得到一個假設最大面積，如果這個面積比當前計算好的面積還要小，該點就可以直接跳過；在上面計算以某點為左上角的矩形面積時，也可以剪枝，剪枝方法同上。具體可以參考代碼注釋。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class
?
Solution {
public
:
????
int
?
maximalRectangle(vector<vector<
char
> > &matrix) {
????????
int
?
row = matrix.size();
????????
if
(row == 0)
return
?
0;
????????
int
?
column = matrix[0].size();
????????
int
?
dp[row][column], res = 0;
????????
memset
(dp, 0,
sizeof
(dp));
????????
//求出所有的dp值
????????
for
(
int
?
i = 0; i < row; i++)
????????????
dp[i][column-1] = (matrix[i][column-1] ==
'1'
);
????????
for
(
int
?
i = 0; i < row; i++)
????????????
for
(
int
?
j = column - 2; j >= 0; j--)
????????????????
if
(matrix[i][j] ==
'1'
)
????????????????????
dp[i][j] = 1 + dp[i][j + 1];
????????
//以每個點作為矩形的左上角計算所得的最大矩形面積
????????
for
(
int
?
i = 0; i < row; i++)
????????
{
????????????
?
????????????
for
(
int
?
j = 0; j < column; j++)
????????????
{
????????????????
//剪枝，column-j是最大寬度，row-i是最大高度
????????????????
if
((column - j) * (row - i) <= res)
break
;
????????????????
int
?
width = dp[i][j];
????????????????
for
(
int
?
k = i; k < row && width > 0; k++)
????????????????
{
????????????????????
//剪枝,row-i是以點(i,j)為左上角的矩形的最大高度
????????????????????
if
(width * (row - i) <= res)
break
;
????????????????????
//計算以(i.j)為左上角，上下邊緣是第i行和第k行的矩形面積
????????????????????
if
(width > dp[k][j])width = dp[k][j];
//矩形寬度要取從第i行到第k行寬度的最小值
????????????????????
res = max(res, width * (k - i + 1));
????????????????
}
????????????
}
????????
}
????????
return
?
res;
????
}
};
|
?
O(n^2)的解法 ：
回想leetcode的另一題計算直方圖最大面積： Largest Rectangle in Histogram ，它可以在O(n)時間內解決，這一題可以轉化成求直方圖最大面積問題，對每一行中的每個位置，計算該位置所在列向上的1的連續個數，這樣每一行中每個位置1的個數就形成了一個直方圖，對每一行調用計算直方圖面積的算法，就可以求出最大的面積。下面代碼中height就是保存每一行每個位置1的個數，并且和上面解法中求dp類似，每一行的height可以由上一行的height求得。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class
?
Solution {
public
:
????
int
?
maximalRectangle(vector<vector<
char
> > &matrix) {
????????
int
?
row = matrix.size();
????????
if
(row == 0)
return
?
0;
????????
int
?
column = matrix[0].size();
????????
int
?
height[column+1], res = 0;
????????
memset
(height, 0,
sizeof
(height));
????????
stack<
int
> S;
????????
for
(
int
?
i = 0; i < row; i++)
????????
{
????????????
stack<
int
>().swap(S);
//清空棧
????????????
bool
?
flag =
false
;
//防止同一height[j]被多次更新
????????????
for
(
int
?
j = 0; j <= column; j++)
????????????
{
????????????????
if
(j < column && flag ==
false
)
????????????????
{
//更新當前行第j列的height值
????????????????????
if
(matrix[i][j] ==
'1'
)
????????????????????
{
????????????????????????
if
(i-1 >=0 && matrix[i-1][j] ==
'1'
)
????????????????????????????
height[j]++;
????????????????????????
else
?
height[j] = 1;
????????????????????
}
????????????????????
else
?
height[j] = 0;
????????????????
}
????????????????
if
?
(S.empty() || height[j] > height[S.top()])
????????????????
{
????????????????????
S.push(j);
????????????????????
flag =
false
;
????????????????
}
????????????????
else
????????????????
{
?????????????????????
int
?
tmp = S.top();
?????????????????????
S.pop();
?????????????????????
res = max(res, height[tmp] * (S.empty() ? j : j-S.top()-1));
?????????????????????
j--;
//保持此次循環中j不變
?????????????????????
flag =
true
;
//height[j]已經更新，無需再次更新
????????????????
}
????????????
}
????????
}
????????
return
?
res;
????
}
};
|
?
其實第一種解法也包含求直方圖最大面積的思想，我們只是把直方圖順時針旋轉了90度，大家可以好好想想看。
?
【版權聲明】轉載請注明出處： http://www.cnblogs.com/TenosDoIt/p/3454877.html
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
