Easy

题目描述

给你一个 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].length
  • 3 <= n <= 100
  • 1 <= grid[i][j] <= 100

解题思路

这是一个典型的滑动窗口问题，需要在矩阵中找到每个 3×3 子矩阵的最大值。

解题思路

方法一：暴力遍历（推荐）

  1. 遍历所有可能的 3×3 子矩阵的左上角位置 (i, j)
  2. 对于每个位置，遍历以该位置为左上角的 3×3 区域，找到最大值
  3. 将最大值存储到结果矩阵的对应位置

由于结果矩阵大小为 (n-2) × (n-2)，所以左上角位置的范围是 0 ≤ i, j ≤ n-3。

优化思路：

  • 可以使用单层循环优化，将 3×3 区域展开为 9 个位置的比较
  • 也可以预处理每行的滑动窗口最大值，但对于此题规模较小，直接暴力即可

时间复杂度： O((n-2)² × 9) = O(n²)，其中 n 是矩阵边长 空间复杂度： O(1)，不考虑输出空间

代码实现

class Solution {
public:
    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> maxLocal(n - 2, vector<int>(n - 2));
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                int maxVal = 0;
                for (int x = i; x < i + 3; x++) {
                    for (int y = j; y < j + 3; y++) {
                        maxVal = max(maxVal, grid[x][y]);
                    }
                }
                maxLocal[i][j] = maxVal;
            }
        }
        
        return maxLocal;
    }
};

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        maxLocal = [[0] * (n - 2) for _ in range(n - 2)]
        
        for i in range(n - 2):
            for j in range(n - 2):
                maxVal = 0
                for x in range(i, i + 3):
                    for y in range(j, j + 3):
                        maxVal = max(maxVal, grid[x][y])
                maxLocal[i][j] = maxVal
        
        return maxLocal

public class Solution {
    public int[][] LargestLocal(int[][] grid) {
        int n = grid.Length;
        int[][] maxLocal = new int[n - 2][];
        
        for (int i = 0; i < n - 2; i++) {
            maxLocal[i] = new int[n - 2];
            for (int j = 0; j < n - 2; j++) {
                int maxVal = 0;
                for (int x = i; x < i + 3; x++) {
                    for (int y = j; y < j + 3; y++) {
                        maxVal = Math.Max(maxVal, grid[x][y]);
                    }
                }
                maxLocal[i][j] = maxVal;
            }
        }
        
        return maxLocal;
    }
}

var largestLocal = function(grid) {
    const n = grid.length;
    const maxLocal = Array(n - 2).fill().map(() => Array(n - 2).fill(0));
    
    for (let i = 0; i < n - 2; i++) {
        for (let j = 0; j < n - 2; j++) {
            let maxVal = 0;
            for (let x = i; x < i + 3; x++) {
                for (let y = j; y < j + 3; y++) {
                    maxVal = Math.max(maxVal, grid[x][y]);
                }
            }
            maxLocal[i][j] = maxVal;
        }
    }
    
    return maxLocal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)遍历 (n-2)² 个位置，每个位置检查 3×3=9 个元素
空间复杂度O(1)只使用常数额外空间，不考虑输出数组