主题切换
LeetCode 每日一题笔记
0. 前言
- 日期：2025.03.20
- 题目：3567.子矩阵的最小绝对差
- 难度：中等
- 标签：数组 矩阵 排序
1. 题目理解
问题描述：
给你一个 m x n 的整数矩阵 grid 和一个整数 k。
对于矩阵 grid 中的每个连续的 k x k 子矩阵，计算其中任意两个 不同值 之间的 最小绝对差 。
返回一个大小为 (m - k + 1) x (n - k + 1) 的二维数组 ans，其中 ans[i][j] 表示以 grid 中坐标 (i, j) 为左上角的子矩阵的最小绝对差。
注意：如果子矩阵中的所有元素都相同，则答案为 0。
子矩阵 (x1, y1, x2, y2) 是一个由选择矩阵中所有满足 x1 <= x <= x2 且 y1 <= y <= y2 的单元格 matrix[x][y] 组成的矩阵。
示例：
输入： grid = [[1,8],[3,-2]], k = 2 输出： [[2]] 解释： 只有一个可能的 k x k 子矩阵：[[1, 8], [3, -2]]。 子矩阵中的不同值为 [1, 8, 3, -2]。 子矩阵中的最小绝对差为 |1 - 3| = 2。因此，答案为 [[2]]。
2. 解题思路
核心观察
算法步骤
3. 代码实现
java
package com.sheeta1998.lec.lc3567;
import java.util.Arrays;
public class lc3600_lc3699.lc3660.Solution {
public int[][] minAbsDiff(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
int[][] ans = new int[m + 1 - k][n + 1 - k];
for (int i = 0; i < m + 1 - k; i++) {
for (int j = 0; j < n + 1 - k; j++) {
int res = Integer.MAX_VALUE;
int[] ints = new int[k * k];
int count = 0;
for (int l = i; l < k + i; l++) {
for (int o = j; o < k + j; o++) {
ints[count++] = grid[l][o];
}
}
int[] sortedInts = Arrays.stream(ints).sorted().toArray();
if (k == 1) {
res = 0;
} else {
for (int l = 1; l < k * k; l++) {
if (sortedInts[l - 1] != sortedInts[l]) {
res = Math.min(res, Math.abs(sortedInts[l] - sortedInts[l-1]));
}
}
}
if (res == Integer.MAX_VALUE) {
res = 0;
}
ans[i][j] = res;
}
}
return ans;
}
}