最大正方形(LeetCode 221)
哪些公司问过
答案要点
- 状态:dp[i][j] 为以 (i,j) 为右下角的最大全 1 正方形边长
- matrix[i][j] 为 0 时 dp 为 0
- 为 1 时 dp[i][j] = min(上, 左, 左上) + 1
- 第一行第一列直接取矩阵的值;记录最大边长,面积为其平方
- 时间 O(m×n),空间可用一维数组压缩到 O(n)
易错点
- 把 dp 定义成面积而不是边长
- 转移时取最大值而不是最小值
- 第一行第一列边界处理错误
- 空间压缩时丢失左上角的旧值
面试官常见追问
- 为什么取三个方向的最小值?
- 怎么把空间压缩到一维?
- 最大矩形怎么做?
- 如果要输出正方形的位置怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场