leetcode
leetcode 2051 ~ 2100
矩阵中的局部最大值

矩阵中的局部最大值

难度:

标签:

题目描述

给你一个大小为 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

代码结果

运行时间: 45 ms, 内存: 16.6 MB


/*
 * 题目思路:
 * 给定一个大小为 n x n 的整数矩阵 grid,要求生成一个大小为 (n - 2) x (n - 2) 的矩阵 maxLocal。
 * 其中 maxLocal[i][j] 等于 grid 中以 i + 1 行和 j + 1 列为中心的 3 x 3 矩阵中的最大值。
 * 
 * 解题步骤:
 * 1. 创建一个新的 (n - 2) x (n - 2) 的矩阵 maxLocal。
 * 2. 使用流式编程遍历 grid 的每一个 3 x 3 矩阵,从 (1, 1) 开始到 (n - 2, n - 2) 结束。
 * 3. 对于每个 3 x 3 矩阵,找到其最大值,并存储到 maxLocal 中。
 */
import java.util.stream.IntStream;

public class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        return IntStream.range(1, n - 1).mapToObj(i ->
            IntStream.range(1, n - 1).map(j ->
                IntStream.range(i - 1, i + 2)
                    .flatMap(x -> IntStream.range(j - 1, j + 2).map(y -> grid[x][y]))
                    .max().orElse(Integer.MIN_VALUE)
            ).toArray()
        ).toArray(int[][]::new);
    }
}

解释

方法:

这道题目的目标是找到每个3x3子矩阵的最大值,并构建一个新的矩阵来存储这些最大值。题解通过双层循环遍历原始矩阵grid的中心元素,对于每个中心元素,检查以它为中心的3x3矩阵,并使用max函数找出这9个元素中的最大值。这个最大值被添加到结果矩阵的对应位置。通过这种方式,我们可以构建出一个(n-2)x(n-2)的新矩阵,其中每个元素代表了原矩阵中对应3x3子矩阵的最大值。

时间复杂度:

O(n^2)

空间复杂度:

O(n^2)

代码细节讲解

🦆
在题解中,为什么选择遍历中心元素作为访问3x3子矩阵的方法?是否有其他可能的遍历策略?
在题解中,遍历中心元素作为访问3x3子矩阵的方法是因为这种方式直观且易于实现。选择中心元素作为遍历的起点可以简化边界处理,因为每个中心元素的位置保证了其周围有足够的空间构成一个完整的3x3矩阵。当然,还有其他遍历策略,例如从矩阵的左上角开始,逐行或逐列遍历每个3x3矩阵的所有元素。这种方法需要更小心地处理边界条件,确保不会访问超出矩阵范围的元素。
🦆
解题代码中,max函数是如何在实际执行中影响算法的性能的?是否存在使用其他数据结构(如堆)来优化查找最大值的过程?
解题代码中,max函数用于找出9个元素中的最大值,这在每个3x3子矩阵中需要重复执行,影响总体性能。虽然max函数对于少量元素(如9个)效率较高,但如果矩阵非常大或需要频繁执行此操作,可能会影响性能。使用其他数据结构如堆(尤其是最大堆)可以优化查找最大值的过程。例如,可以为整个矩阵维护一个滑动窗口的最大堆,但这样的实现复杂度较高,对于只涉及9个元素的简单场景,使用max函数通常是效率和实现简便性的最佳平衡。
🦆
题解中提到的每个中心元素对应的3x3矩阵的最大值是如何确保不越界的?例如,对于矩阵的边缘元素,如何处理3x3矩阵可能超出原矩阵边界的情况?
题解中通过限制中心元素的遍历范围确保不越界。具体来说,中心元素的遍历从 grid[1][1] 开始,到 grid[n-2][n-2] 结束,其中 n 是原矩阵的行数(或列数,因为矩阵是方形的)。这种遍历方式保证了每个选定的中心元素周围都有足够的单元格构成完整的3x3矩阵,从而避免了边缘问题。对于矩阵的边缘元素,因为它们无法成为任何3x3子矩阵的中心,所以在这种遍历策略下自然被排除在外。

相关问题