85-maximal-rectangle.md

85. Maximal Rectangle - 最大矩形

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

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

---

题目标签：Stack / Array / Hash Table / Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	52 ms	11.9 MB

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if (!n) return 0;
        int m = matrix[0].size();
        if (!m) return 0;
        
        vector<vector<int> > rc(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++) {
                rc[i][j] = rc[i - 1][j] + rc[i][j - 1] - rc[i - 1][j - 1] + (matrix[i - 1][j - 1] == '1' ? 1 : 0);
            }
        }
        int res = 0;
        vector<vector<int> > dp(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = max(matrix[i - 1][j - 1] == '1' ? 1 : 0, max(dp[i - 1][j], dp[i][j - 1]));
                if (matrix[i - 1][j - 1]) {
                    bool flag = false;
                    for (int x = i - 1; x >= 0; x--) {
                        if (flag) break;
                        for (int y = j - 1; y >= 0; y--) {
                            int t = rc[i][j] - rc[x][j] - rc[i][y] + rc[x][y];
                            if (t == (i - x) * (j - y)) {
                                dp[i][j] = max(dp[i][j], t);
                            } else {
                                if (y == j - 1) {
                                    flag = true;
                                }
                                break;
                            }
                        }
                    }
                }
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();