What is the core pattern used to solve the Maximal Square problem?

The problem is primarily solved using state transition dynamic programming, where each matrix cell tracks the largest square that can end at that position.

Can the Maximal Square problem be solved without dynamic programming?

While it's possible to solve it with brute force, dynamic programming offers an efficient solution, reducing time complexity from O(m * n^2) to O(m * n).

How do you optimize space in Maximal Square's solution?

Space can be optimized by storing only the current and previous rows of the DP matrix, reducing space complexity from O(m * n) to O(n).

What happens if the matrix contains all 0's in the Maximal Square problem?

If the matrix consists solely of 0's, the largest square will have an area of 0, as no 1's are available to form a square.

What is the expected output for a 1x1 matrix in the Maximal Square problem?

For a 1x1 matrix, the output will either be 0 or 1, depending on whether the single cell contains a 0 or 1.

#221

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。示例 1：输入： matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1…

数组动态规划矩阵

题目描述

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

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

lightbulb

解题思路

方法一：动态规划

我们定义 $dp[i + 1][j + 1]$ 表示以下标 $(i, j)$ 作为正方形右下角的最大正方形边长。答案为所有 $dp[i + 1][j + 1]$ 中的最大值。

状态转移方程为：

dp[i + 1][j + 1] = \begin{cases} 0 & \textit{if } matrix[i][j] = '0' \\ \min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1 & \textit{if } matrix[i][j] = '1' \end{cases}

时间复杂度 $O(m\times n)$ ，空间复杂度 $O(m\times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

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)]
        mx = 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 + 1], dp[i + 1][j], dp[i][j]) + 1
                    mx = max(mx, dp[i + 1][j + 1])
        return mx * mx

speed

复杂度分析

指标	值
时间	complexity is O(m * n) where m and n are the dimensions of the matrix, as each cell is processed once. Space complexity can be optimized to O(n) by keeping only the current and previous rows of the DP matrix, reducing the overall space usage from O(m * n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Assess the candidate's ability to optimize space in dynamic programming solutions.
question_mark
Evaluate how well the candidate explains and uses state transitions in dynamic programming.
question_mark
Check if the candidate can identify the trade-offs between time and space complexities.

warning

常见陷阱

外企场景

error
Forgetting to initialize the first row and first column of the DP matrix correctly.
error
Using a brute force approach to check every potential square without leveraging dynamic programming.
error
Not optimizing space by reducing the DP matrix to only necessary rows.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to find the largest square of 1's within a submatrix of the matrix.
arrow_right_alt
Consider a version where the matrix size can vary during runtime or input.
arrow_right_alt
Challenge the candidate to solve the problem without using dynamic programming for a brute force solution.

help

常见问题

外企场景

继续练习

#329 矩阵中的最长递增路径 #85 最大矩形 #64 最小路径和