题目描述
思路解析动画文字版
记住这一句:一个 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题