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

这道题到底在问什么

输入

grid=[[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]

输出

[[9,9],[8,6]]

输入

grid=[[1,1,1],[1,2,1],[1,1,1]]

输出

[[2]]

最优解：一步一步想明白

1. 3记住这一句:一个 3 乘 3 的窗口在网格上滑,停在哪里就把窗口里九个数的最大值填到结果对应的格子。下面从左上角的窗口开始,一个窗口一个窗口地看。
2. 4输入:4×4这是输入的 grid,四行四列。为什么结果是 2 乘 2 呢?因为一个 3 乘 3 的窗口在 4 格宽的行里,左上角只能放在第 0 列或第 1 列两个位置,再往右窗口就出界了,竖着同理。所以窗口一共有两行两列共四个落点,结果自然是 2 乘 2。心里先有这个数。
3. 5框出窗口先把窗口框出来给你看。左上角这个 3 乘 3 的方块,盖住了 grid 左上九个数,它们的最大值就是结果 maxLocal 第 0 行第 0 列的值。橙色框住的九格就是一个窗口。接下来我把窗口里的数一行一行扫过去,盯着当前见过的最大值,看它落在哪一格。
4. 6左上方块开工窗口停在左上角,左上角坐标是 (0,0),它盖住的九个数就是 grid 前三行前三列。目标是把这九个数里的最大值,填到结果 maxLocal 的 (0,0)。我准备一个记号,叫它当前最大,一开始还没看任何数。现在开始一行一行扫窗口。
5. 7第 1 行,最大 9先扫窗口最上面一行,三个数是 9、9、8。从没有数到有数,当前最大直接记成这一行里最大的 9,它在 (0,0),我用紫色把它点亮。
6. 8第 2 行,最大 9接着扫窗口的第 2 行,三个数是 5、6、2。这三个数都没超过之前的 9,当前最大不变,紫色格子还停在 (0,0)。
7. 9第 3 行,最大 9接着扫窗口的第 3 行,三个数是 8、2、6。这三个数都没超过之前的 9,当前最大不变,紫色格子还停在 (0,0)。 九个数全扫完了,这个窗口的最大值就定在 9。
8. 10左上 → 9这个窗口九个数扫完,最大是 9,在 (0,0),我把它染成绿色。把 9 写进结果 maxLocal 的 (0,0),右边答案面板多了一行,已填格子数涨到 1。窗口接着往下一个位置滑。
9. 11右上方块开工窗口从上一处滑到 (0,1),这是右上方块,盖住 grid 第 0 到 2 行、第 1 到 3 列。老规矩,当前最大清零重来,再把这九个数一行一行扫一遍,找出这个窗口自己的最大值。
10. 12第 1 行,最大 9先扫窗口最上面一行,三个数是 9、8、1。从没有数到有数,当前最大直接记成这一行里最大的 9,它在 (0,1),我用紫色把它点亮。
11. 13第 2 行,最大 9接着扫窗口的第 2 行,三个数是 6、2、6。这三个数都没超过之前的 9,当前最大不变,紫色格子还停在 (0,1)。
12. 14第 3 行,最大 9接着扫窗口的第 3 行,三个数是 2、6、4。这三个数都没超过之前的 9,当前最大不变,紫色格子还停在 (0,1)。 九个数全扫完了,这个窗口的最大值就定在 9。
13. 15右上 → 9这个窗口九个数扫完,最大是 9,在 (0,1),我把它染成绿色。把 9 写进结果 maxLocal 的 (0,1),右边答案面板多了一行,已填格子数涨到 2。窗口接着往下一个位置滑。
14. 16左下方块开工窗口从上一处滑到 (1,0),这是左下方块,盖住 grid 第 1 到 3 行、第 0 到 2 列。老规矩,当前最大清零重来,再把这九个数一行一行扫一遍,找出这个窗口自己的最大值。
15. 17第 1 行,最大 6先扫窗口最上面一行,三个数是 5、6、2。从没有数到有数,当前最大直接记成这一行里最大的 6,它在 (1,1),我用紫色把它点亮。
16. 18第 2 行,最大 8接着扫窗口的第 2 行,三个数是 8、2、6。这一行里冒出了更大的 8,当前最大被顶到 (2,0),紫色格子跟着挪过去。
17. 19第 3 行,最大 8接着扫窗口的第 3 行,三个数是 6、2、2。这三个数都没超过之前的 8,当前最大不变,紫色格子还停在 (2,0)。 九个数全扫完了,这个窗口的最大值就定在 8。
18. 20左下 → 8这个窗口九个数扫完,最大是 8,在 (2,0),我把它染成绿色。把 8 写进结果 maxLocal 的 (1,0),右边答案面板多了一行,已填格子数涨到 3。窗口接着往下一个位置滑。
19. 21右下方块开工窗口从上一处滑到 (1,1),这是右下方块,盖住 grid 第 1 到 3 行、第 1 到 3 列。老规矩,当前最大清零重来,再把这九个数一行一行扫一遍,找出这个窗口自己的最大值。
20. 22第 1 行,最大 6先扫窗口最上面一行,三个数是 6、2、6。从没有数到有数,当前最大直接记成这一行里最大的 6,它在 (1,1),我用紫色把它点亮。
21. 23第 2 行,最大 6接着扫窗口的第 2 行,三个数是 2、6、4。这三个数都没超过之前的 6,当前最大不变,紫色格子还停在 (1,1)。
22. 24第 3 行,最大 6接着扫窗口的第 3 行,三个数是 2、2、2。这三个数都没超过之前的 6,当前最大不变,紫色格子还停在 (1,1)。 九个数全扫完了,这个窗口的最大值就定在 6。
23. 25右下 → 6这个窗口九个数扫完,最大是 6,在 (1,1),我把它染成绿色。把 6 写进结果 maxLocal 的 (1,1),右边答案面板多了一行,已填格子数涨到 4。四个窗口到这就全填完了。
24. 26答案:[[9,9],[8,6]]四个窗口全部滑完了。左上窗口能看到顶上那两个 9,右上窗口能看到 (0,1) 这个 9;左下窗口的最大值是第 2 行的 8;右下窗口九个数最大是 6。把四个答案按位置拼起来,结果就是 [[9,9],[8,6]]。整道题从头到尾就是一个 3 乘 3 窗口滑过去、每停一处取一次最大值。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问