题目描述
思路解析
一句话答案：LeetCode 2373 矩阵中的局部最大值：一个 3 乘 3 窗口在网格上滑，每停一处把窗口九个数取最大填进结果格；结果本就只有 (n-2)² 个格，暴力枚举已是最优，时间 O(n²)、空间 O(1)。
结果网格为什么小一圈，每格填的是什么
给一张 n 行 n 列的整数网格 grid，要生成一张 (n-2) 行 (n-2) 列的网格 maxLocal。maxLocal 第 i 行第 j 列，等于 grid 里以第 i+1 行、第 j+1 列为中心那个 3 乘 3 方块里的最大值——也就是把 grid 上每一个挨着的 3 乘 3 方块的最大值都挑出来、按位置拼成结果。题面例子 grid=[[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]，边长 4，横竖各能放下两个 3 乘 3 方块，结果就是 2 乘 2 的 [[9,9],[8,6]]。
拿窗口中心当基准往四周扩，行列偏移最先算岔
以每个方块的中心格为基准去凑那九个数，是这题最容易算岔的一种写法。中心在 grid 里的坐标是 (i+1, j+1)，往四周扩要同时管 i+1 上下、j+1 左右一圈加减，行列偏移很容易写反或差一格。另一个念头是担心这样一格格枚举太慢——但结果本身就有大约 n² 个格子，每格固定看九个数，总量就是 O(n²)，渐进意义上已经没法更快，暴力枚举反倒最干净。
改用左上角 (i,j) 当基准，九个数直接取最大
把基准从中心换成窗口的左上角，一切就顺了。让结果格 (i,j) 对应的窗口，左上角正好落在 grid 的 (i,j)，那这个窗口盖住的就是第 i 到 i+2 行、第 j 到 j+2 列共九个数，maxLocal[i][j] 填的就是这九个数的最大值。外层两重循环让 i、j 各从 0 走到 n-3，把结果格挨个填满；内层把 i..i+2、j..j+2 这九个位置扫一遍取最大。i 最大到 n-3 时，i+2 正好是 n-1、最后一行，窗口永远贴着边、不会滑出界。
拿题面的 4 乘 4 网格把四个窗口挨个算
结果是 2 乘 2，四个窗口对应四个左上角。左上角 (0,0)：盖住第 0 到 2 行、第 0 到 2 列，九个数是 9、9、8、5、6、2、8、2、6，最大 9，填进 maxLocal(0,0)。左上角 (0,1) 往右挪一列，九个数 9、8、1、6、2、6、2、6、4，最大还是 9。左上角 (1,0) 往下挪一行，九个数 5、6、2、8、2、6、6、2、2，最大 8。左上角 (1,1) 在右下，九个数 6、2、6、2、6、4、2、2、2，最大 6。四个值按位置拼起来是 [[9,9],[8,6]]。
只看九个数的代价，还有哪些地方最容易写反
复杂度上，结果有 (n-2)² 个格子，约等于 n²；每格固定扫九个数取最大，是常数工作量，乘起来抹掉常数就是时间 O(n²)。额外空间只用了几个循环变量和一个记最大值的临时量，是 O(1)，结果网格是题目要返回的产物，不算额外开销。
有几处坑得先避开：n=3 时只放得下一个窗口，结果是 1 乘 1，填的就是整张网格的最大值；C++、Java 里记最大值的初值要设成 0 再取最大，因为格子值都不小于 1，若像求最小那样拿很大的数起步再取最大就整个反了；结果尺寸也务必开成 (n-2)×(n-2)，开成 n 乘 n 会多出没意义的空行空列。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一句:一个 3 乘 3 的窗口在网格上滑,停在哪里就把窗口里九个数的最大值填到结果对应的格子。下面从左上角的窗口开始,一个窗口一个窗口地看。
先看输入 · 4 乘 4 的网格：这是输入的 grid,四行四列。为什么结果是 2 乘 2 呢?因为一个 3 乘 3 的窗口在 4 格宽的行里,左上角只能放在第 0 列或第 1 列两个位置,再往右窗口就出界了,竖着同理。所以窗口一共有两行两列共四个落点,结果自然是 2 乘 2。心里先有这个数。
窗口概念 · 左上角先框出一个 3 乘 3：先把窗口框出来给你看。左上角这个 3 乘 3 的方块,盖住了 grid 左上九个数,它们的最大值就是结果 maxLocal 第 0 行第 0 列的值。橙色框住的九格就是一个窗口。接下来我把窗口里的数一行一行扫过去,盯着当前见过的最大值,看它落在哪一格。
窗口滑到 (0,0) · 求 maxLocal(0,0)：窗口停在左上角,左上角坐标是 (0,0),它盖住的九个数就是 grid 前三行前三列。目标是把这九个数里的最大值,填到结果 maxLocal 的 (0,0)。我准备一个记号,叫它当前最大,一开始还没看任何数。现在开始一行一行扫窗口。
扫窗口第 1 行 · 数值 9、9、8：先扫窗口最上面一行,三个数是 9、9、8。从没有数到有数,当前最大直接记成这一行里最大的 9,它在 (0,0),我用紫色把它点亮。
扫窗口第 2 行 · 数值 5、6、2：接着扫窗口的第 2 行,三个数是 5、6、2。这三个数都没超过之前的 9,当前最大不变,紫色格子还停在 (0,0)。
扫窗口第 3 行 · 数值 8、2、6：接着扫窗口的第 3 行,三个数是 8、2、6。这三个数都没超过之前的 9,当前最大不变,紫色格子还停在 (0,0)。 九个数全扫完了,这个窗口的最大值就定在 9。
左上方块结算 · maxLocal(0,0) = 9：这个窗口九个数扫完,最大是 9,在 (0,0),我把它染成绿色。把 9 写进结果 maxLocal 的 (0,0),右边答案面板多了一行,已填格子数涨到 1。窗口接着往下一个位置滑。
窗口滑到 (0,1) · 求 maxLocal(0,1)：窗口从上一处滑到 (0,1),这是右上方块,盖住 grid 第 0 到 2 行、第 1 到 3 列。老规矩,当前最大清零重来,再把这九个数一行一行扫一遍,找出这个窗口自己的最大值。
扫窗口第 1 行 · 数值 9、8、1：先扫窗口最上面一行,三个数是 9、8、1。从没有数到有数,当前最大直接记成这一行里最大的 9,它在 (0,1),我用紫色把它点亮。
扫窗口第 2 行 · 数值 6、2、6：接着扫窗口的第 2 行,三个数是 6、2、6。这三个数都没超过之前的 9,当前最大不变,紫色格子还停在 (0,1)。
扫窗口第 3 行 · 数值 2、6、4：接着扫窗口的第 3 行,三个数是 2、6、4。这三个数都没超过之前的 9,当前最大不变,紫色格子还停在 (0,1)。 九个数全扫完了,这个窗口的最大值就定在 9。
右上方块结算 · maxLocal(0,1) = 9：这个窗口九个数扫完,最大是 9,在 (0,1),我把它染成绿色。把 9 写进结果 maxLocal 的 (0,1),右边答案面板多了一行,已填格子数涨到 2。窗口接着往下一个位置滑。
窗口滑到 (1,0) · 求 maxLocal(1,0)：窗口从上一处滑到 (1,0),这是左下方块,盖住 grid 第 1 到 3 行、第 0 到 2 列。老规矩,当前最大清零重来,再把这九个数一行一行扫一遍,找出这个窗口自己的最大值。
扫窗口第 1 行 · 数值 5、6、2：先扫窗口最上面一行,三个数是 5、6、2。从没有数到有数,当前最大直接记成这一行里最大的 6,它在 (1,1),我用紫色把它点亮。
扫窗口第 2 行 · 数值 8、2、6：接着扫窗口的第 2 行,三个数是 8、2、6。这一行里冒出了更大的 8,当前最大被顶到 (2,0),紫色格子跟着挪过去。
扫窗口第 3 行 · 数值 6、2、2：接着扫窗口的第 3 行,三个数是 6、2、2。这三个数都没超过之前的 8,当前最大不变,紫色格子还停在 (2,0)。 九个数全扫完了,这个窗口的最大值就定在 8。
左下方块结算 · maxLocal(1,0) = 8：这个窗口九个数扫完,最大是 8,在 (2,0),我把它染成绿色。把 8 写进结果 maxLocal 的 (1,0),右边答案面板多了一行,已填格子数涨到 3。窗口接着往下一个位置滑。
窗口滑到 (1,1) · 求 maxLocal(1,1)：窗口从上一处滑到 (1,1),这是右下方块,盖住 grid 第 1 到 3 行、第 1 到 3 列。老规矩,当前最大清零重来,再把这九个数一行一行扫一遍,找出这个窗口自己的最大值。
扫窗口第 1 行 · 数值 6、2、6：先扫窗口最上面一行,三个数是 6、2、6。从没有数到有数,当前最大直接记成这一行里最大的 6,它在 (1,1),我用紫色把它点亮。
扫窗口第 2 行 · 数值 2、6、4：接着扫窗口的第 2 行,三个数是 2、6、4。这三个数都没超过之前的 6,当前最大不变,紫色格子还停在 (1,1)。
扫窗口第 3 行 · 数值 2、2、2：接着扫窗口的第 3 行,三个数是 2、2、2。这三个数都没超过之前的 6,当前最大不变,紫色格子还停在 (1,1)。 九个数全扫完了,这个窗口的最大值就定在 6。
右下方块结算 · maxLocal(1,1) = 6：这个窗口九个数扫完,最大是 6,在 (1,1),我把它染成绿色。把 6 写进结果 maxLocal 的 (1,1),右边答案面板多了一行,已填格子数涨到 4。四个窗口到这就全填完了。
回放 · 四个窗口全部求出：四个窗口全部滑完了。左上窗口能看到顶上那两个 9,右上窗口能看到 (0,1) 这个 9;左下窗口的最大值是第 2 行的 8;右下窗口九个数最大是 6。把四个答案按位置拼起来,结果就是 [[9,9],[8,6]]。整道题从头到尾就是一个 3 乘 3 窗口滑过去、每停一处取一次最大值。
边界想清:n=3 只有一个窗口结果 1×1、全相同取任一值、被所有窗口盖住的大数会出现在每个结果格。
面试重点:滑动 3×3 窗口逐格取最大、窗口固定 3×3 时枚举九格已是 O(n²) 最优、注意结果是 (n-2)² 且用左上角当基准。
参考代码
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 largestLocal(self, grid: List[List[int]]) -> List[List[int]]: n = len(grid) ans = [[0] * (n - 2) for _ in range(n - 2)] for i in range(n - 2): for j in range(n - 2): ans[i][j] = max( grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3) ) return ans复杂度
- 时间：O(n²)，结果矩阵有 (n-2) 乘 (n-2) 个格子,约等于 n² 个;每个格子固定看 9 个数取最大,是常数工作量。9 乘 (n-2)² 抹掉常数就是 O(n²),随边长平方增长
- 空间：O(1)，按额外占用算。只用了几个循环变量和一个记最大值的临时量,都是常数;结果矩阵是题目要求返回的产物,不计入额外空间。所以额外空间是 O(1),不随 n 变大
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问这个暴力解法还能优化吗?
追问写的时候最容易出的错是什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
被围绕的区域
LeetCode 130 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题