矩阵中的局部最大值 图解题解

结果网格为什么小一圈，每格填的是什么

给一张 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 会多出没意义的空行空列。

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> ans(n - 2, vector<int>(n - 2));
        for (int i = 0; i < n - 2; ++i) {
            for (int j = 0; j < n - 2; ++j) {
                for (int x = i; x <= i + 2; ++x) {
                    for (int y = j; y <= j + 2; ++y) {
                        ans[i][j] = max(ans[i][j], grid[x][y]);
                    }
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        int[][] ans = new int[n - 2][n - 2];
        for (int i = 0; i < n - 2; ++i) {
            for (int j = 0; j < n - 2; ++j) {
                for (int x = i; x <= i + 2; ++x) {
                    for (int y = j; y <= j + 2; ++y) {
                        ans[i][j] = Math.max(ans[i][j], grid[x][y]);
                    }
                }
            }
        }
        return ans;
    }
}