Maximal Rectangle
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.
思路
每一行以上，按Largest Rectangle in Histogram的思路来。
解题
c++版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
41class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m=matrix.size();
if(m==0) return 0;
int n=matrix[0].size();
int maxArea=0;
int height[m][n];
for(int j=0;j<n;j++){
int h=0;
for(int i=0;i<m;i++){
if(matrix[i][j]=='1')
h++;
else
h=0;
height[i][j]=h;
}
}
stack<int> stk;
for(int i=0;i<m;i++){
int j=0;
while(j<n){
if(stk.empty() || height[i][stk.top()] <= height[i][j]){
stk.push(j++);
}else {
int t = stk.top();
stk.pop();
maxArea = max(maxArea, height[i][t] * (stk.empty() ? j: j- stk.top() - 1));
}
}
while(!stk.empty()){
int t = stk.top();
stk.pop();
maxArea = max(maxArea, height[i][t] * (stk.empty() ? j: j- stk.top() - 1));
}
}
return maxArea;
}
};
