题目描述
思路解析动画文字版
记住这条:把每个格子向下、向右的连续 1 个数先算好,四条边是否全 1 就靠四个角的计数和 k 比大小。边长从大到小,首次命中即最大。
总览 · 原始 4×4 网格(还没处理)：这是一张 4×4 网格,行号 i、列号 j。左上角 (0,0) 和右下角 (3,3) 是 0,其余十四格都是 1。还没处理的格子先显示原始的 0 或 1,处理过的格子会换成「向下连续数、向右连续数」这两个值。我们要找的最大正方形,答案会落在 9。
预处理 · 算 down/right 第 (3,3) 格：第 3 行第 3 列是 0,连续 1 的链子在这里断掉,向下、向右都记 0。
预处理 · 算 down/right 第 (3,2) 格：第 3 行第 2 列是 1。下面已经到头,下面没有格子(算作 0),所以向下只算自己这 1 个;向右接着右边那格的 0 个,连上自己向右连续 1 个。
预处理 · 算 down/right 第 (3,1) 格：第 3 行第 1 列是 1。下面已经到头,下面没有格子(算作 0),所以向下只算自己这 1 个;向右接着右边那格的 1 个,连上自己向右连续 2 个。
预处理 · 算 down/right 第 (3,0) 格：第 3 行第 0 列是 1。下面已经到头,下面没有格子(算作 0),所以向下只算自己这 1 个;向右接着右边那格的 2 个,连上自己向右连续 3 个。
预处理 · 算 down/right 第 (2,3) 格：第 2 行第 3 列是 1。向下接着下面那格的 0 个,连上自己向下连续 1 个;右边已经到头,右边没有格子(算作 0),所以向右只算自己这 1 个。
预处理 · 算 down/right 第 (2,2) 格：第 2 行第 2 列是 1。向下接着下面那格的 1 个,连上自己向下连续 2 个;向右接着右边那格的 1 个,连上自己向右连续 2 个。
预处理 · 算 down/right 第 (2,1) 格：第 2 行第 1 列是 1。向下接着下面那格的 1 个,连上自己向下连续 2 个;向右接着右边那格的 2 个,连上自己向右连续 3 个。
预处理 · 算 down/right 第 (2,0) 格：第 2 行第 0 列是 1。向下接着下面那格的 1 个,连上自己向下连续 2 个;向右接着右边那格的 3 个,连上自己向右连续 4 个。
预处理 · 算 down/right 第 (1,3) 格：第 1 行第 3 列是 1。向下接着下面那格的 1 个,连上自己向下连续 2 个;右边已经到头,右边没有格子(算作 0),所以向右只算自己这 1 个。
预处理 · 算 down/right 第 (1,2) 格：第 1 行第 2 列是 1。向下接着下面那格的 2 个,连上自己向下连续 3 个;向右接着右边那格的 1 个,连上自己向右连续 2 个。
预处理 · 算 down/right 第 (1,1) 格：第 1 行第 1 列是 1。向下接着下面那格的 2 个,连上自己向下连续 3 个;向右接着右边那格的 2 个,连上自己向右连续 3 个。
预处理 · 算 down/right 第 (1,0) 格：第 1 行第 0 列是 1。向下接着下面那格的 2 个,连上自己向下连续 3 个;向右接着右边那格的 3 个,连上自己向右连续 4 个。
预处理 · 算 down/right 第 (0,3) 格：第 0 行第 3 列是 1。向下接着下面那格的 2 个,连上自己向下连续 3 个;右边已经到头,右边没有格子(算作 0),所以向右只算自己这 1 个。
预处理 · 算 down/right 第 (0,2) 格：第 0 行第 2 列是 1。向下接着下面那格的 3 个,连上自己向下连续 4 个;向右接着右边那格的 1 个,连上自己向右连续 2 个。
预处理 · 算 down/right 第 (0,1) 格：第 0 行第 1 列是 1。向下接着下面那格的 3 个,连上自己向下连续 4 个;向右接着右边那格的 2 个,连上自己向右连续 3 个。
预处理 · 算 down/right 第 (0,0) 格：第 0 行第 0 列是 0,连续 1 的链子在这里断掉,向下、向右都记 0。
预处理完成 · 每格都带上了 ↓下扩、→右扩：十六个格子全部处理完。现在每格都写着向下、向右两个连续 1 的个数,0 的格子是 ↓0 →0。接下来从最大的边长开始,看看能不能拼出一个四边全 1 的正方形。
试边长 k=4 · 左上角 (0,0)：先试最大的边长 4,整张网格只有一个左上角 (0,0)。可它本身就是 0,向右、向下的连续计数都是 0,上边都凑不齐,边长 4 直接出局。
试边长 k=3 · 左上角 (0,0)：边长缩到 3。第一个左上角还是 (0,0),它是 0,连第一条边都开不了头,跳过,换下一个左上角。
试边长 k=3 · 左上角 (0,1) · 查上边：换到左上角 (0,1),它是 1,可以开工。先查上边,这条边占第 0 行的列 1 到 3,正好是从 (0,1) 向右数 3 格。看它的向右计数 right 是 3,不小于 3,说明这 3 格全是 1,上边过关。
试边长 k=3 · 左上角 (0,1) · 查左边：再查左边,这条边占第 1 列的行 0 到 2,是从 (0,1) 向下数 3 格。看它的向下计数 down 是 4,比 3 还多,这 3 格当然全是 1,左边也过关。
试边长 k=3 · 左上角 (0,1) · 查下边：接着查下边。下边的起点是左下角 (2,1),这条边从它向右数 3 格。看 (2,1) 的向右计数 right 是 3,不小于 3,下边全是 1,过关。注意下边看的是左下角,别看错成左上角。
试边长 k=3 · 左上角 (0,1) · 查右边：最后查右边。右边的起点是右上角 (0,3),从它向下数 3 格。看 (0,3) 的向下计数 down 是 3,正好够 3,右边全是 1。四条边全部通过,边长 3 的正方形找到了。
命中 · 左上角 (0,1) 的 3×3 正方形：把这圈边框点亮:左上角 (0,1),覆盖第 0 到 2 行、第 1 到 3 列。整圈 8 个边框格全是 1,里面那格是什么都无所谓。因为我们是从大边长往小试的,4 凑不出、3 第一个命中,这个 3 就是最大的。它覆盖的 9 个格子面积是 3 乘 3 等于 9,这就是答案。
边界都能手验:中间是 0 仍算 9;单行最多凑 1×1;全 0 返回 0。
面试三连:两张计数表把边检查降到 O(1);四条边各看起点角的计数;O(n³) 已够、早停首次命中即返回。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def largest1BorderedSquare(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) down = [[0] * n for _ in range(m)] right = [[0] * n for _ in range(m)] for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): if grid[i][j]: down[i][j] = down[i + 1][j] + 1 if i + 1 < m else 1 right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1 for k in range(min(m, n), 0, -1): for i in range(m - k + 1): for j in range(n - k + 1): if ( down[i][j] >= k and right[i][j] >= k and right[i + k - 1][j] >= k and down[i][j + k - 1] >= k ): return k * k return 0复杂度
- 时间：O(m·n·min(m,n))，预处理两张表是 O(m·n)。枚举阶段:边长 k 有 min(m,n) 种,每种要扫 O(m·n) 个左上角,每个左上角靠预处理的计数 O(1) 查四条边。方阵时约为 O(n³),n ≤ 100 完全够用
- 空间：O(m·n)，按峰值算:down、right 两张和网格同样大的表,都是 m×n,空间是 O(m·n);若网格是 n×n 方阵就是 O(n²)。没有递归,不额外吃栈
易错点
面试追问把动画讲成自己的话
追问为什么要预处理 down 和 right 两张表?
追问四条边分别看哪个角的计数?
追问复杂度能再压吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长公共子序列
LeetCode 1143 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题