题目描述
思路解析
一句话答案：LeetCode 764 最大加号标志：对每格数上下左右四方向连续 1 的长度、取四者最小当臂长，四遍方向 DP 压完再取全表最大值，因为加号被最短的一条臂卡死。时间 O(n²)、空间 O(n²)。
什么样的十字才算一个 k 阶加号
给一个 n × n 的方格，除 mines 列出的地雷是 0，其余都是 1。一个 k 阶加号有一个中心格，从中心往上下左右各伸一条长 k-1 的臂，中心和四条臂必须全踩在 1 上，求盘面能摆的最大阶数 k，没有 1 就返回 0。坐标写成（行号,列号），都从 0 数起。题面例子 n=4、地雷 (0,1) 和 (2,3)，答案 2：走一格全是 1，再走就撞雷或出界。
为什么挨个中心去扩加号会白扫太多次
让每个格子轮流当中心、四个方向一格格往外探，n² 个中心每个最坏花 O(n) 探臂，整套就是 O(n³)。慢就慢在探臂：一个中心要确认自己 k 阶，四条臂各查 k-1 个格子，臂最坏伸到 n，相邻中心的臂还大段重叠、被反复重数。
一个格子能撑多大加号，被四条臂里最短的卡死
先别管加号，只问每个格子朝某方向连着能数出几个 1（遇雷或边界就断）。它当中心时，臂长超不过任何一个方向的连续 1 长度——四条臂要同时成立，只要一条方向 1 不够长，加号就伸不出去。四个方向里最短的那条卡住它，一条臂短，加号就缩到那条的长度。
四个方向各扫一遍，为什么能共用同一张表
开一张和盘面同样大的 dp 表（dp 即动态规划：把每格算过的结果存表里、后面直接取用不重算），dp[i][j] 记以 (i,j) 为中心能撑的臂长。陆地格先填 n（臂长上限，后面往下压——每遍都跟表里的值取较小的、把臂长往小里改，叫压），地雷格填 0。分四遍：逐行从左往右数向左、从右往左数向右（从左扫过去，是在数每格往左能连几个 1），逐列从上往下数向上、从下往上数向下；每数出一个方向的长度就和 dp 当前值取 min，遇 1 加一、遇地雷清零，保证数的是不含雷的连续 1。四个方向互相独立，共用一张表、四遍压完剩的就是四方向最小。
拿 4×4 两颗地雷，把四遍扫描亲手压一遍
用题面 n=4、地雷 (0,1) 和 (2,3)，dp 先填陆地 4、地雷 0。第一遍数向左：第 1 行整行 1，压成 1、2、3、4；第 0 行到 (0,1) 撞雷清零，成 1、0、1、2。第二遍从右往左取 min：(1,3) 向左本是 4，可在最右边、向右只有 1，min(4,1)=1 压回。左右叠完，中间两列留 2、贴边成 1。
第三遍数向上取 min：(1,1) 头顶就是地雷、向上只有 1，横向的 2 被压成 1；(1,2) 上方畅通、向上有 2，min(2,2) 保住 2。第四遍数向下取 min：最底一行向下都只有 1、整行压成 1，而 (2,1) 下方还有一格、向下 2 保住 2。四遍压完，全表只剩 (1,2) 和 (2,1) 是 2，取全表最大得 2。
取 min 写成 max，加号为什么会被夸大
四遍每遍走完整张 n×n 的表，时间是它的常数倍 O(n²)；只用一张 dp 表反复取 min，空间 O(n²)。地雷再多也不改复杂度，规模只看 n。取 min 写成 max，等于一条臂够长就行、加号被夸大成最长那条；数连续 1 遇地雷忘清零，跨地雷的两段会被接成一段；陆地格初值填 0 或 1 而非够大的 n，第一遍 min 就把臂长误压低。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句口诀:加号的臂长被最短的那条方向卡住,所以是四个方向连续 1 的长度取最小值。下面每一帧都在套它。
原始盘面 · 两颗地雷：这就是 4 × 4 的盘面。红色的 0 是地雷,在 (0,1) 和 (2,3);其余绿色的格子都是 1。加号的每一格都必须落在绿色的 1 上。
看一个候选中心 (2,1)：先用 (2,1) 试手。把中心点紫,再往上下左右各探一格:上是 (1,1)、下是 (3,1)、左是 (2,0)、右是 (2,2),四个邻居都是 1。四个方向都能走出 1 格,所以这里能撑起 2 阶加号。
另开一张同样大小的 dp 表,每格记「以它为中心的臂长」。臂长再长也超不过 n,所以陆地格先填 4 这个上限,两颗地雷格直接填 0。接下来四遍扫描会把这些 4 一点点压小。
第一遍,逐行从左往右扫,数每个格子向左方向(含自己)连续有几个 1。遇到 1 就加一,遇到地雷就清零重来。先拿第 1 行找感觉。
第 1 行整行都是 1,没有地雷打断,所以向左长度一路累加成 1、2、3、4。这一行越往右,左臂越长。
再看第 0 行。(0,0) 是 1,记 1;到 (0,1) 撞上地雷,长度清零记 0;过了雷,(0,2) 重新从 1 开始,(0,3) 接着是 2。地雷会把连续段切断,这点很关键。
四行都这么扫完,整张 dp 表现在装的是每个格子的向左臂长。注意这只是四个方向里的一个,接下来三遍会用更短的方向把它继续压小。
第二遍反过来,逐行从右往左数向右臂长,数出来后和表里的值取最小。盯住 (1,3):它向左臂长是 4,可它在最右边,向右一步都迈不出去。
果然,(1,3) 向右只有 1,min(4, 1) 等于 1,它被压回 1。最左边的 (1,0) 正相反,向左只有 1。取 min 的意义就在这:一个方向再长,只要另一个方向短,加号就撑不大。
两遍叠完,每格装的是左右两个方向的较小值,也就是这一行里横着能伸多远。靠中间的格子(像第 1、2 列)还保留着 2,边上的都被压成了 1。
第三遍换方向,逐列从上往下数向上臂长,继续取 min。看第 1 列:顶上 (0,1) 是地雷,所以 (1,1) 向上只有 1,(2,1) 是 2,(3,1) 是 3。地雷同样会把竖向也切断。
(1,1) 头顶就是地雷,向上只有 1,横向的 2 被压成了 1。而 (1,2) 上方一路畅通,向上有 2,和横向的 2 取 min 还是 2,稳稳保住。能不能当大加号的中心,这一步开始分化。
三遍叠完,每格已经是左、右、上三个方向的最小值。只剩最后一个方向,向下。
最后一遍,逐列从下往上数向下臂长,再取一次 min。最底下那一行 (第 3 行) 每个格子向下都迈不出去,向下臂长全是 1。
所以第 3 行整行被向下臂长 1 压成了 1,贴着边界的格子当不了大加号的中心。而 (2,1) 下方还有一格,向下臂长是 2,min(2, 2) 保持 2,它扛住了四个方向。
四个方向都扫完了,这张表就是最终答案表。每格的值,正是以它为中心能撑起的最大加号阶数。能看到只有 (1,2) 和 (2,1) 两个格子是 2,其余都是 1 或 0。
最后一步,把整张表扫一遍取最大值。最大就是 2,出现在 (1,2) 和 (2,1)。这就是题目要的答案,和开头说的 2 对上了。
答案加号 · 中心 (2,1)：回到盘面,把 (2,1) 这个 2 阶加号画出来:中心加上下左右各一格,五个格子全是 1,稳稳成立。再大一阶就要伸到第二格,可那样会撞到边界或地雷,所以到 2 为止。
为什么到 2 为止 · 想再伸一格：想把 (2,1) 升到 3 阶吗?那上臂要伸到 (0,1),可那里是地雷;左臂要伸到 (2,-1),已经出了边界。任何一条臂走不通,加号就升不上去,所以 (2,1) 封顶在 2 阶。
另一个 2 阶加号 · 中心 (1,2)：(1,2) 也是一样,上下左右各一格都是 1,同样是 2 阶。两个并列第一,答案取它们的阶数 2,具体在哪个中心并不重要。
边界先想清:只要有一个 1,答案至少是 1(它自己就是 1 阶加号);整张没有 1 才返回 0。1 阶加号其实就是一个孤立的中心点,不需要伸出任何臂。
面试重点:四方向独立所以能复用一张表,以及复杂度只看 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 *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int: dp = [[n] * n for _ in range(n)] for x, y in mines: dp[x][y] = 0 for i in range(n): left = right = up = down = 0 for j, k in zip(range(n), reversed(range(n))): left = left + 1 if dp[i][j] else 0 right = right + 1 if dp[i][k] else 0 up = up + 1 if dp[j][i] else 0 down = down + 1 if dp[k][i] else 0 dp[i][j] = min(dp[i][j], left) dp[i][k] = min(dp[i][k], right) dp[j][i] = min(dp[j][i], up) dp[k][i] = min(dp[k][i], down) return max(max(v) for v in dp)复杂度
- 时间：O(n²)，四个方向各扫一遍 n × n 的表,常数倍的网格遍历
- 空间：O(n²)，一张和网格同样大的 dp 表,复用它存四方向的 min
易错点
面试追问把动画讲成自己的话
追问能不能不用四张方向表, 只用一张 dp 表?
追问如果地雷非常多、几乎填满网格, 复杂度会变吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
多米诺和托米诺平铺
LeetCode 790 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题