矩阵中的局部最大值
难度:
标签:
题目描述
给你一个大小为 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子矩阵的方法?是否有其他可能的遍历策略?
▷🦆
解题代码中,max函数是如何在实际执行中影响算法的性能的?是否存在使用其他数据结构(如堆)来优化查找最大值的过程?
▷🦆
题解中提到的每个中心元素对应的3x3矩阵的最大值是如何确保不越界的?例如,对于矩阵的边缘元素,如何处理3x3矩阵可能超出原矩阵边界的情况?
▷