221. 最大正方形
题目描述
输入一个 m x n 的矩阵 matrix，每个元素是字符 '0' 或 '1'。
在矩阵中找一个所有格子都是 '1' 的正方形，让它尽可能大。返回这个正方形的面积；如果矩阵里没有 '1'，返回 0。
示例 1
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：4
解释：第 2、3 行与第 3、4 列交叉处是一个边长为 2 的全 '1' 正方形，面积为 4。
示例 2
输入：matrix = [["0","1"],["1","0"]] 输出：1
解释：只能找到边长为 1 的正方形，面积为 1。
示例 3
输入：matrix = [["0"]] 输出：0
解释：矩阵中没有 '1'。
数据范围
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]为'0'或'1'。
解题思路
设 dp[i+1][j+1] 为以 (i,j) 为右下角的全 1 正方形的最大边长。若该格是 1，它能向左上扩展多大，受限于左边、上边、左上三个方向中最短的那一个：三者取最小再加 1。多开一行一列的 0 作为边界，避免判断越界。答案是最大边长的平方。
为什么正确
dp[i+1][j+1] = min(左上, 上, 左) + 1：三个以相邻格为右下角的正方形拼起来，恰好覆盖边长加 1 的正方形。
复杂度分析
时间 O(mn)，空间 O(mn)（可压缩到 O(n)）。
易错点
题目返回的是面积而不是边长，最后要平方；另外矩阵元素是字符 '1'，不是数字 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
best = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
dp[i + 1][j + 1] = min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1
best = max(best, dp[i + 1][j + 1])
return best * bestclass Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
int best = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
dp[i + 1][j + 1] = Math.min(dp[i][j], Math.min(dp[i][j + 1], dp[i + 1][j])) + 1;
best = Math.max(best, dp[i + 1][j + 1]);
}
}
}
return best * best;
}
}class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
int best = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
dp[i + 1][j + 1] = min({dp[i][j], dp[i][j + 1], dp[i + 1][j]}) + 1;
best = max(best, dp[i + 1][j + 1]);
}
}
}
return best * best;
}
};func maximalSquare(matrix [][]byte) int {
m, n := len(matrix), len(matrix[0])
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
best := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == '1' {
dp[i+1][j+1] = min(dp[i][j], dp[i][j+1], dp[i+1][j]) + 1
best = max(best, dp[i+1][j+1])
}
}
}
return best * best
}var maximalSquare = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
let best = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === '1') {
dp[i + 1][j + 1] = Math.min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1;
best = Math.max(best, dp[i + 1][j + 1]);
}
}
}
return best * best;
};function maximalSquare(matrix: string[][]): number {
const m = matrix.length, n = matrix[0].length;
const dp: number[][] = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
let best = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === '1') {
dp[i + 1][j + 1] = Math.min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1;
best = Math.max(best, dp[i + 1][j + 1]);
}
}
}
return best * best;
}