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ù)雜度至少為O(n^4) (計算復(fù)雜度是我們把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時，寬度為第一行中從第一個位置起連續(xù)的1的個數(shù)，為4，面積為4 * 1 = 4
矩形高度是2時，第二行從第一個位置起連續(xù)1的個數(shù)是3，寬度為min(3,4) = 3，面積為3*2 = 6
矩形高度為3時，第三行從第一個位置起連續(xù)1的個數(shù)是1，寬度為min(1,3) = 1，面積為1*3 = 3
矩形高度為4時，第四行從第一個位置起連續(xù)1的個數(shù)是0，寬度為min(0,1) = 0，面積為0*4 = 0
后面的行就不用計算了，因為上一行計算的寬度是0，下面所有寬度都是0
因此以(0,0)為左上角的矩形的最大面積是6，計算以某一點為左上角的矩形的最大面積復(fù)雜度是O(n)。
注意到上面我們用到了信息“從某一行某個位置開始連續(xù)的1的個數(shù)”，這個我們可以通過動態(tài)規(guī)劃求得：設(shè)dp[i][j]是從點(i,j)開始，這一行連續(xù)1的個數(shù)，動態(tài)規(guī)劃方程如下：???????????????????????????????????????????????????????????????? 本文地址
- 初始條件：dp[i][column-1] = (matrix[i][column-1] == '1') （column是matrix的列數(shù)）
- dp[i][j] = (matrix[i][j] == '1') ?? 1 + dp[i][j + 1] : 0 ，(從方程看出我們應(yīng)該從每一行的后往前計算)
計算dp復(fù)雜度O(n^2)，枚舉左上角位置以及計算以該位置為左上角的矩形最大面積復(fù)雜度是O(n^2*n)=O(n^3)，總的復(fù)雜度是O(n^3)
這個算法還可以優(yōu)化，枚舉到某個點時我們可以假設(shè)該點右下方全是1，得到一個假設(shè)最大面積，如果這個面積比當(dāng)前計算好的面積還要小，該點就可以直接跳過；在上面計算以某點為左上角的矩形面積時，也可以剪枝，剪枝方法同上。具體可以參考代碼注釋。
|
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)時間內(nèi)解決，這一題可以轉(zhuǎn)化成求直方圖最大面積問題，對每一行中的每個位置，計算該位置所在列向上的1的連續(xù)個數(shù)，這樣每一行中每個位置1的個數(shù)就形成了一個直方圖，對每一行調(diào)用計算直方圖面積的算法，就可以求出最大的面積。下面代碼中height就是保存每一行每個位置1的個數(shù)，并且和上面解法中求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
)
????????????????
{
//更新當(dāng)前行第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--;
//保持此次循環(huán)中j不變
?????????????????????
flag =
true
;
//height[j]已經(jīng)更新，無需再次更新
????????????????
}
????????????
}
????????
}
????????
return
?
res;
????
}
};
|
?
其實第一種解法也包含求直方圖最大面積的思想，我們只是把直方圖順時針旋轉(zhuǎn)了90度，大家可以好好想想看。
?
【版權(quán)聲明】轉(zhuǎn)載請注明出處： http://www.cnblogs.com/TenosDoIt/p/3454877.html
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
