-
Notifications
You must be signed in to change notification settings - Fork 0
/
13_April.cpp
41 lines (35 loc) · 1.05 KB
/
13_April.cpp
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
class Solution {
public:
int largestRectangleArea(vector<int>&histo){
stack<int>st;
int maxA = 0;
int n = histo.size();
for(int i = 0; i <= n ; i++){
while(!st.empty() && (i == n || histo[st.top()] >= histo[i])){
int height = histo[st.top()];
st.pop();
int width;
if(st.empty()) width = i;
else width = i - st.top() - 1;
maxA = max(maxA, width * height);
}
st.push(i);
}
return maxA;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int maxArea = 0;
int n = matrix.size();
int m = matrix[0].size();
vector<int>height(m,0);
for(int i = 0; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(matrix[i][j] == '1')height[j]++;
else height[j] = 0;
}
int area = largestRectangleArea(height);
maxArea = max(maxArea,area);
}
return maxArea;
}
};