-
Notifications
You must be signed in to change notification settings - Fork 0
/
MaxRectangle.cpp
38 lines (38 loc) · 1.15 KB
/
MaxRectangle.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
class MaxRectangle {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.size() == 0) {
return 0;
}
int n = matrix[0].size();
vector<int> heights(n);
int largest = 0;
for (vector<char>& row : matrix) {
for (int j = 0; j < n; ++j) {
if (row[j] == '1') {
heights[j]++;
} else {
heights[j] = 0;
}
}
largest = max(largest, get_max(heights));
}
return largest;
}
private:
int get_max(vector<int>& heights) {
int res = 0;
deque<int> stack;
for (int right = 0; right <= heights.size(); ++right) {
int cur = right == heights.size() ? 0 : heights[right];
while (!stack.empty() && heights[stack.back()] >= cur) {
int height = heights[stack.back()];
stack.pop_back();
int left = stack.empty() ? -1 : stack.back();
res = max(res, height * (right - left - 1));
}
stack.push_back(right);
}
return res;
}
};