LeetCode 题解工作台
矩阵中的局部最大值
给你一个大小为 n x n 的整数矩阵 grid 。 生成一个大小为 (n - 2) x (n - 2) 的整数矩阵 maxLocal ，并满足： maxLocal[i][j] 等于 grid 中以 i + 1 行和 j + 1 列为中心的 3 x 3 矩阵中的 最大值 。 换句话说，我们希望找出 …
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·matrix
答案摘要
我们可以枚举每个 $3 \times 3$ 的矩阵，求出每个 $3 \times 3$ 的矩阵中的最大值，然后将这些最大值放入答案矩阵中。 时间复杂度 ，其中 是矩阵的边长。忽略答案矩阵的空间消耗，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个大小为 n x n 的整数矩阵 grid 。
生成一个大小为 (n - 2) x (n - 2) 的整数矩阵 maxLocal ，并满足：
maxLocal[i][j]等于grid中以i + 1行和j + 1列为中心的3 x 3矩阵中的 最大值 。
换句话说，我们希望找出 grid 中每个 3 x 3 矩阵中的最大值。
返回生成的矩阵。
示例 1：
输入：grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]] 输出：[[9,9],[8,6]] 解释：原矩阵和生成的矩阵如上图所示。 注意，生成的矩阵中，每个值都对应 grid 中一个相接的 3 x 3 矩阵的最大值。
示例 2：
输入：grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]] 输出：[[2,2,2],[2,2,2],[2,2,2]] 解释：注意，2 包含在 grid 中每个 3 x 3 的矩阵中。
提示：
n == grid.length == grid[i].length3 <= n <= 1001 <= grid[i][j] <= 100
解题思路
方法一：枚举
我们可以枚举每个 的矩阵，求出每个 的矩阵中的最大值，然后将这些最大值放入答案矩阵中。
时间复杂度 ，其中 是矩阵的边长。忽略答案矩阵的空间消耗，空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) because each element in the (n-2)x(n-2) output matrix requires checking 3x3 elements. Space complexity is O(n^2) for storing the result matrix of size (n-2)x(n-2). |
| 空间 | O(N \cdot N) |
面试官常问的追问
外企场景- question_mark
Check if candidate correctly identifies the 3x3 window pattern and iterates over all valid starting indices.
- question_mark
Observe whether candidate handles edge cases with the smallest possible matrix size, n=3.
- question_mark
Listen for explanations of how nested loops avoid out-of-bounds errors and maintain O(n^2) performance.
常见陷阱
外企场景- error
Incorrectly iterating past n-2 causing index out-of-bounds errors.
- error
Forgetting to initialize the local maximum properly within each 3x3 window.
- error
Confusing row and column indices while populating the result matrix.
进阶变体
外企场景- arrow_right_alt
Find the minimum value in every 3x3 submatrix instead of the maximum.
- arrow_right_alt
Compute local sums or averages for each 3x3 window rather than maximums.
- arrow_right_alt
Extend the pattern to rectangular k x k submatrices for variable k.