85. Maximal Rectangle - cocoder39/coco39_LC GitHub Wiki
Notes 2022:
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
heights = [0] * n
area = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
heights[j] += 1
else:
heights[j] = 0
area = max(area, self.helper(heights))
return area
def helper(self, heights):
stack = []
heights.append(-1)
area = 0
for i, height in enumerate(heights):
while stack and height <= stack[-1][1]:
_, h = stack.pop()
left = stack[-1][0] if stack else -1
area = max(area, h * (i - left - 1))
stack.append((i, height))
heights.pop()
return area
======================================================== solution 1: based on 84. Largest Rectangle in Histogram which takes O(n) time and memory. O(m * n) time and O(n) memory
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
vector<int> heights(n);
int area = 0;
for (int i = 0; i < m; i++) {
stack<int> s;
for (int j = 0; j < n; j++) {
heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
}
area = max(area, largestRectangleArea(heights));
}
return area;
}
private:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
int area = 0;
heights.push_back(-1);
for (int i = 0; i < heights.size(); i++) {
while (! s.empty() && heights[i] <= heights[s.top()]) {
int height = heights[s.top()];
s.pop();
int width = i - (s.empty() ? -1 : s.top()) - 1;
area = max(area, height * width);
}
s.push(i);
}
heights.pop_back();
return area;
}
};
solution 2: for each bin matrix[i][j], we first get its height, which is the number of consecutive '1' starts from it. Then we pay attention to the left and right bounds of the rectangle with this height. Take left bound as an example. if matrix[i][j] == '1', then the left bound is depends on both left bound of current row cur_left and matrix[i - 1][j]. Otherwise matrix[i][j] == 0, then we advance left bound of current row for unprocessed bins in current row. Meanwhile, we set lefts[j] to be 0, here lefts[j] is of no use for this bin because matrix[i][j] == '0'. However, it is important for calculating left bound of matrix[i + 1][j]. since from matrix[i + 1][j]'s perspective, left bound of matrix[i][j] is same as 0 if matrix[i][j] == '0'
matrix:
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
left:
0 0 0 3 0 0 0
0 0 2 3 2 0 0
0 1 2 3 2 1 0
rights:
6 6 6 3 6 6 6
6 6 4 3 4 6 6
6 5 4 3 4 5 6
O(m * n) time and O(n) memory
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
vector<int> heights(n);
vector<int> lefts(n); //lefts[j] is left bound of rectangle whose height is heights[j]
vector<int> rights(n, n - 1);
int area = 0;
for (int i = 0; i < m; i++) {
int cur_left = 0;
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
heights[j]++;
//left bound is greater bound of current row and previous row
lefts[j] = max(cur_left, lefts[j]);
}
else {
heights[j] = 0;
//from matrix[i + 1][j]' perspective, left bound of matrxi[i][j] same as 0 if matrix[i][j] == '0'
lefts[j] = 0;
cur_left = j + 1; //advance left bound of current row
}
}
int cur_right = n - 1;
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j] == '1') {
rights[j] = min(cur_right, rights[j]);
area = max(area, heights[j] * (rights[j] - lefts[j] + 1));
}
else {
rights[j] = n - 1;
cur_right = j - 1;
}
}
}
return area;
}
Notes on Aug. 15, 2020: main idea is to iterate every possible height and find the max width. The width is bounded by cur row and also previous rows who contribute to the height. If a previous row contributes to the height (i.e., node == "1"), the left/right bound of the row could impact the left/right bound of current node. If the previous row doesn't contribute to the height (i.e., node == "0"), then it does't impact the left/right bound of current row so set lefts[j] = 0 or rights[j] = n