• 2024-03-19 leetcode写题记录
  • 85. 最大矩形
    • 题目链接
    • 题意
    • 解法

2024-03-19 leetcode写题记录

85. 最大矩形

题目链接

85. 最大矩形

题意

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

解法

先对每个元素求出其往上能延伸的高度，然后再对每一行作为下边界考虑，考虑行里每个元素作为连续区间里最小元素的情况，从而就变成了求每个元素往左右两边找比自身的高度更低的元素所在的位置，用单调栈跑一遍就行。

class Solution {
   public:
    int maximalRectangle(vector<vector<char>> matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> h(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (matrix[i][j] == '0') continue;
                if (i == 0)
                    h[i][j] = 1;
                else
                    h[i][j] = h[i - 1][j] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            stack<int> s;
            vector<int> l(m, 0), r(m, m - 1);
            for (int j = 0; j < m; ++j) {
                while (!s.empty() && h[i][s.top()] >= h[i][j]) {
                    r[s.top()] = j - 1;
                    s.pop();
                }
                if (!s.empty()) l[j] = s.top() + 1;
                s.push(j);
            }
            for (int j = 0; j < m; ++j) 
                ans = max(ans, (r[j] - l[j] + 1) * h[i][j]);
        }
        return ans;
    }
};