LeetCode 2373: Largest Local Values in a Matrix (3×3 Sliding Window Maximum)
LeetCode 2373MatrixWindowSimulationToday we solve LeetCode 2373 - Largest Local Values in a Matrix.
Source: https://leetcode.com/problems/largest-local-values-in-a-matrix/
English
Problem Summary
Given an n × n integer matrix grid, build an (n-2) × (n-2) matrix maxLocal where each cell is the maximum value inside the corresponding 3 × 3 submatrix of grid.
Key Insight
Each output cell maps directly to one fixed 3 × 3 window in the input. So we can enumerate all top-left corners (i, j) and compute the local maximum in 9 checks.
Brute Force and Limitations
A naive idea is still to scan every 3 × 3 block. Here that is already optimal enough because each block has constant size (9). Total work is proportional to output cell count.
Optimal Algorithm Steps
1) Let m = n - 2; create result matrix ans[m][m].
2) For each i in [0, m-1] and j in [0, m-1], examine grid[i..i+2][j..j+2].
3) Track the maximum among those 9 elements.
4) Set ans[i][j] to that maximum.
Complexity Analysis
Time: O((n-2)^2 × 9) = O(n^2).
Space: O((n-2)^2) for output only.
Common Pitfalls
- Returning an n × n matrix by mistake.
- Off-by-one bounds when iterating window starts.
- Mixing up window start (i, j) and offset (di, dj).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[][] largestLocal(int[][] grid) {
int n = grid.length;
int m = n - 2;
int[][] ans = new int[m][m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
int mx = Integer.MIN_VALUE;
for (int di = 0; di < 3; di++) {
for (int dj = 0; dj < 3; dj++) {
mx = Math.max(mx, grid[i + di][j + dj]);
}
}
ans[i][j] = mx;
}
}
return ans;
}
}func largestLocal(grid [][]int) [][]int {
n := len(grid)
m := n - 2
ans := make([][]int, m)
for i := 0; i < m; i++ {
ans[i] = make([]int, m)
for j := 0; j < m; j++ {
mx := grid[i][j]
for di := 0; di < 3; di++ {
for dj := 0; dj < 3; dj++ {
if grid[i+di][j+dj] > mx {
mx = grid[i+di][j+dj]
}
}
}
ans[i][j] = mx
}
}
return ans
}class Solution {
public:
vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
int n = (int)grid.size();
int m = n - 2;
vector<vector<int>> ans(m, vector<int>(m));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
int mx = grid[i][j];
for (int di = 0; di < 3; ++di) {
for (int dj = 0; dj < 3; ++dj) {
mx = max(mx, grid[i + di][j + dj]);
}
}
ans[i][j] = mx;
}
}
return ans;
}
};class Solution:
def largestLocal(self, grid: list[list[int]]) -> list[list[int]]:
n = len(grid)
m = n - 2
ans = [[0] * m for _ in range(m)]
for i in range(m):
for j in range(m):
mx = grid[i][j]
for di in range(3):
for dj in range(3):
mx = max(mx, grid[i + di][j + dj])
ans[i][j] = mx
return ansvar largestLocal = function(grid) {
const n = grid.length;
const m = n - 2;
const ans = Array.from({ length: m }, () => Array(m).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < m; j++) {
let mx = grid[i][j];
for (let di = 0; di < 3; di++) {
for (let dj = 0; dj < 3; dj++) {
mx = Math.max(mx, grid[i + di][j + dj]);
}
}
ans[i][j] = mx;
}
}
return ans;
};中文
题目概述
给定一个 n × n 的整数矩阵 grid，构造大小为 (n-2) × (n-2) 的矩阵 maxLocal，其中每个元素等于原矩阵对应 3 × 3 子矩阵中的最大值。
核心思路
输出矩阵的每个位置都唯一对应输入中的一个 3 × 3 窗口。我们枚举窗口左上角 (i, j)，在 9 个元素里求最大值即可。
暴力解法与不足
看起来像暴力，但这里窗口大小固定就是 9，因此每个输出点都是常数代价，整体复杂度已经是 O(n^2) 量级，足够高效。
最优算法步骤
1）令 m = n - 2，创建结果矩阵 ans[m][m]。
2）枚举每个窗口左上角 (i, j)。
3）遍历偏移 di, dj ∈ [0,2]，在 9 个元素中更新最大值。
4）把最大值写入 ans[i][j]。
复杂度分析
时间复杂度：O((n-2)^2 × 9) = O(n^2)。
空间复杂度：O((n-2)^2)（仅输出矩阵）。
常见陷阱
- 把结果矩阵错误地开成 n × n。
- 窗口起点循环边界少一位或多一位。
- 把窗口起点与偏移坐标混用，导致索引错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[][] largestLocal(int[][] grid) {
int n = grid.length;
int m = n - 2;
int[][] ans = new int[m][m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
int mx = Integer.MIN_VALUE;
for (int di = 0; di < 3; di++) {
for (int dj = 0; dj < 3; dj++) {
mx = Math.max(mx, grid[i + di][j + dj]);
}
}
ans[i][j] = mx;
}
}
return ans;
}
}func largestLocal(grid [][]int) [][]int {
n := len(grid)
m := n - 2
ans := make([][]int, m)
for i := 0; i < m; i++ {
ans[i] = make([]int, m)
for j := 0; j < m; j++ {
mx := grid[i][j]
for di := 0; di < 3; di++ {
for dj := 0; dj < 3; dj++ {
if grid[i+di][j+dj] > mx {
mx = grid[i+di][j+dj]
}
}
}
ans[i][j] = mx
}
}
return ans
}class Solution {
public:
vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
int n = (int)grid.size();
int m = n - 2;
vector<vector<int>> ans(m, vector<int>(m));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
int mx = grid[i][j];
for (int di = 0; di < 3; ++di) {
for (int dj = 0; dj < 3; ++dj) {
mx = max(mx, grid[i + di][j + dj]);
}
}
ans[i][j] = mx;
}
}
return ans;
}
};class Solution:
def largestLocal(self, grid: list[list[int]]) -> list[list[int]]:
n = len(grid)
m = n - 2
ans = [[0] * m for _ in range(m)]
for i in range(m):
for j in range(m):
mx = grid[i][j]
for di in range(3):
for dj in range(3):
mx = max(mx, grid[i + di][j + dj])
ans[i][j] = mx
return ansvar largestLocal = function(grid) {
const n = grid.length;
const m = n - 2;
const ans = Array.from({ length: m }, () => Array(m).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < m; j++) {
let mx = grid[i][j];
for (let di = 0; di < 3; di++) {
for (let dj = 0; dj < 3; dj++) {
mx = Math.max(mx, grid[i + di][j + dj]);
}
}
ans[i][j] = mx;
}
}
return ans;
};
Comments