学习动态规划-子矩阵

1，全为1的最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

来源：221. 最大正方形

解题思路：

dp[i][j]表示以matrix[i][j]为右下角的全1的正方形的最大边长。

很明显，当matrix[i][j]==0时，dp[i][j]=0；
当matrix[i][j]==1时，dp[i][j]的值为左上、上、左3个节点的最小值+1，即dp[i][j] = min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}+1。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        int result = 0;
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] - '0';
            result = max(dp[i][0], result);
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j] - '0';
            result = max(dp[0][j], result);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '0') continue;
                int t1 = dp[i-1][j];
                int t2 = dp[i][j-1];
                int t3 = dp[i-1][j-1];
                dp[i][j] = min(min(t1, t2), t3) + 1;
                result = max(result, dp[i][j]);
            }
        }
        return result * result;
    }
};

2，全为1的正方形个数

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

来源：1277. 统计全为 1 的正方形子矩阵

解题思路：

思路同题1，dp[i][j]表示以matrix[i][j]为右下角的全1的正方形的最大边长。

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // dp[i][j]以matrix[i][j]为右下角能组成的最大正方形的边长
        vector<vector<int>> dp = matrix;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) continue;
                dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
            }
        }
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result += dp[i][j];
            }
        }
        return result;
    }
};

3，全为1的最大矩形

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

来源：85. 最大矩形

解题思路：

按行将二维数组分解成多个子矩阵，前1行、前2行、前3行和前4行组成的子矩阵分别如下：

每个子矩阵利用 84. 柱状图中最大的矩形 的解法计算最大矩形。

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        vector<int> dp(matrix[0].size() + 2);
        int result = 0;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i][j] == '0') {
                    dp[j+1] = 0;
                } else {
                    dp[j+1] += 1;
                }
            }
            result = max(result, largestRectangleArea(dp));
        }
        return result;
    }
    int largestRectangleArea(vector<int>& heights) { // heights两边已经添加了0
        stack<int> s;
        int result = 0;

        for (int i = 0; i < heights.size(); i++) {
            while (!s.empty() && heights[s.top()] > heights[i]) {
                // 出栈，并计算area
                int height = heights[s.top()];
                s.pop();
                int width = (i - 1) - (s.top() + 1) + 1;
                result = max(result, height * width);
            }
            s.push(i);
        }
        
        return result;
    }
};