LeetCode 221. 最大正方形

◎

本节目标

用以当前位置为右下角的最大边长，求字符矩阵中全 1 正方形的最大面积。

返回网格与路径动态规划框架

查看 LeetCode 原题

题意与约束

给定由 '0' 和 '1' 组成的矩阵，返回只含 '1' 的最大正方形面积。

第一反应与重复子问题

逐个枚举边长会重复检查重叠区域。若固定右下角，只需知道三个相邻方向已经能延展多长。

状态定义与转移推导

dp[r][c] 是以该格为右下角的最大边长。若为 '1'，边长为 min(上,左,左上)+1；若为 '0' 则为 0。答案返回最大边长平方。

正确性依据

更大正方形必须同时有足够长的上、左、左上三个邻域，短板限制可扩展边长；三者满足时新增一行一列即可构成该边长。

样例执行过程

中心为 '0' 的 3×3 矩阵会把中心状态清零，周围最大边长均只能为 1，面积为 1。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size(), best = 0;
        vector<int> dp(cols + 1, 0);
        for (int row = 1; row <= rows; row++) {
            int diagonal = 0;
            for (int col = 1; col <= cols; col++) {
                int above = dp[col];
                if (matrix[row - 1][col - 1] == '1') {
                    dp[col] = min({dp[col], dp[col - 1], diagonal}) + 1;
                    best = max(best, dp[col]);
                } else {
                    dp[col] = 0;
                }
                diagonal = above;
            }
        }
        return best * best;
    }
};

Python

Python 3

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        cols = len(matrix[0])
        dp = [0] * (cols + 1)
        best = 0
        for row in matrix:
            diagonal = 0
            for col, cell in enumerate(row, 1):
                above = dp[col]
                if cell == '1':
                    dp[col] = min(dp[col], dp[col - 1], diagonal) + 1
                    best = max(best, dp[col])
                else:
                    dp[col] = 0
                diagonal = above
        return best * best

复杂度分析

时间 O(rc)，空间 O(c)。

边界与易错点

• 返回的是面积而不是边长。
• 滚动数组更新前先保存旧 dp[c] 作为左上角。
• 字符 '1' 不能按整数 1 直接比较。

模式迁移

以右下角为状态的思想可迁移到最大矩形等局部几何题，但后者需要维护高度并配合单调栈。