题目描述
思路解析动画文字版
记住这句口诀:加号的臂长被最短的那条方向卡住,所以是四个方向连续 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题