给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
[“1”,”0”,”1”,”0”,”0”],
[“1”,”0”,”1”,”1”,”1”],
[“1”,”1”,”1”,”1”,”1”],
[“1”,”0”,”0”,”1”,”0”]
]
输出: 6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法1：栈
对每一行统计一次各个列的高度，dp[j]=(matrix[i][j]==’1’)?dp[j+1]:0;
然后对每一行应用84题解法。
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
44
45
| class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n=matrix.size();
if(n==0)
return 0;
int m=matrix[0].size();
int i,j;
int res=0;
vector<int> dp(m,0);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
dp[j]=(matrix[i][j]=='1')?dp[j]+1:0;
}
res=max(res,largestRectangleArea(dp));
}
return res;
}
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
st.push(-1);
int n=heights.size();
int i;
int res=0;
for(i=0;i<n;i++)
{
while(st.top()!=-1&&heights[st.top()]>heights[i])
{
int c=heights[st.top()];
st.pop();
res=max(res,(i-st.top()-1)*c);
}
st.push(i);
}
while(st.top()!=-1)
{
int c=heights[st.top()];
st.pop();
res=max(res,(i-st.top()-1)*c);
}
return res;
}
};
|
解法2：动态规划
用height记录当前行为底,第j列高度是多少.
用left记录第i行为底，第j列构建最大矩形的左边界（从j列往前左边第一个小于height[j]的位置）
用right记录第j行为底，第j列构建的最大矩形的右边界(从j列往后最右边第一个小于height[i]的位置)
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
44
45
| class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n=matrix.size();
if(n==0)
return 0;
int m=matrix[0].size();
int i,j;
int res=0;
vector<int> height (m,0);
vector<int> left(m,0);
vector<int> right(m,m);
int cur_left=0,cur_right=m;
for(i=0;i<n;i++)
{
cur_left=0;
cur_right=m;
for(j=0;j<m;j++)
height[j]=(matrix[i][j]=='1')?(height[j]+1):0;
for(j=0;j<m;j++)
{
if(matrix[i][j]=='1')
left[j]=max(left[j],cur_left);
else
{
left[j]=0;
cur_left=j+1;
}
}
for(j=m-1;j>=0;j--)
{
if(matrix[i][j]=='1')
right[j]=min(right[j],cur_right);
else
{
right[j]=m;
cur_right=j;
}
}
for(j=0;j<m;j++)
res=max(res,height[j]*(right[j]-left[j]));
}
return res;
}
};
|