LeetCode 85. Maximal Rectangle

Posted on Edited on In 
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
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        const int rows = matrix.size();
        if (rows == 0) return 0;
        const int cols = matrix[0].size();
        vector<vector<int>> left(rows, vector<int>(cols, 0));
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (matrix[r][c] == '1')
                    left[r][c] = (c == 0 ? 0 : left[r][c - 1]) + 1;
        int ans = 0;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (matrix[r][c] == '1') {
                    int width = left[r][c];
                    int area = width;
                    for (int k = r - 1; k >= 0; --k) {
                        width = min(width, left[k][c]);
                        area = max(area, width * (r - k + 1));
                    }
                    ans = max(ans, area);
                }
        return ans;
    }
};
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
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        const int rows = matrix.size();
        if (rows == 0) return 0;
        const int cols = matrix[0].size();
        vector<vector<int>> left(rows, vector<int>(cols, 0));
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (matrix[r][c] == '1')
                    left[r][c] = (c == 0 ? 0 : left[r][c - 1]) + 1;
        int ans = 0;
        for (int c = 0; c < cols; ++c) {
            vector<int> up(rows, 0), down(rows, 0);
            stack<int> s;
            for (int r = 0; r < rows; ++r) {
                while (!s.empty() && left[s.top()][c] >= left[r][c])
                    s.pop();
                up[r] = s.empty() ? -1 : s.top();
                s.push(r);
            }
            s = stack<int>();
            for (int r = rows - 1; r >= 0; --r) {
                while (!s.empty() && left[s.top()][c] >= left[r][c])
                    s.pop();
                down[r] = s.empty() ? rows : s.top();
                s.push(r);
            }
            for (int r = 0; r < rows; ++r) {
                int height = down[r] - up[r] - 1;
                ans = max(ans, height * left[r][c]);
            }
        }
        return ans;
    }
};