LeetCode 题解工作台
子矩阵的最小绝对差
给你一个 m x n 的整数矩阵 grid 和一个整数 k 。 对于矩阵 grid 中的每个连续的 k x k 子矩阵 ，计算其中任意两个 不同 值 之间的 最小绝对差 。 返回一个大小为 (m - k + 1) x (n - k + 1) 的二维数组 ans ，其中 ans[i][j] 表示以 g…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
我们可以枚举所有可能的 $k \times k$ 子矩阵的左上角坐标 $(i, j)$，对于每个子矩阵，我们可以提取出其中的所有元素，放入一个列表 中。然后对 进行排序，接着计算相邻的不同元素之间的绝对差，找到最小的绝对差值。最后将结果存储在一个二维数组中。 时间复杂度 $O((m - k + 1) \times (n - k + 1) \times k^2 \log(k))$，其中 和 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你一个 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] 组成的矩阵。
示例 1：
输入： grid = [[1,8],[3,-2]], k = 2
输出： [[2]]
解释：
- 只有一个可能的
k x k子矩阵：[[1, 8], [3, -2]]。 - 子矩阵中的不同值为
[1, 8, 3, -2]。 - 子矩阵中的最小绝对差为
|1 - 3| = 2。因此，答案为[[2]]。
示例 2：
输入： grid = [[3,-1]], k = 1
输出： [[0,0]]
解释：
- 每个
k x k子矩阵中只有一个不同的元素。 - 因此，答案为
[[0, 0]]。
示例 3：
输入： grid = [[1,-2,3],[2,3,5]], k = 2
输出： [[1,2]]
解释：
- 有两个可能的
k × k子矩阵：- 以
(0, 0)为起点的子矩阵：[[1, -2], [2, 3]]。- 子矩阵中的不同值为
[1, -2, 2, 3]。 - 子矩阵中的最小绝对差为
|1 - 2| = 1。
- 子矩阵中的不同值为
- 以
(0, 1)为起点的子矩阵：[[-2, 3], [3, 5]]。- 子矩阵中的不同值为
[-2, 3, 5]。 - 子矩阵中的最小绝对差为
|3 - 5| = 2。
- 子矩阵中的不同值为
- 以
- 因此，答案为
[[1, 2]]。
提示：
1 <= m == grid.length <= 301 <= n == grid[i].length <= 30-105 <= grid[i][j] <= 1051 <= k <= min(m, n)
解题思路
方法一：枚举
我们可以枚举所有可能的 子矩阵的左上角坐标 ，对于每个子矩阵，我们可以提取出其中的所有元素，放入一个列表 中。然后对 进行排序，接着计算相邻的不同元素之间的绝对差，找到最小的绝对差值。最后将结果存储在一个二维数组中。
时间复杂度 ，其中 和 分别是矩阵的行数和列数，而 是子矩阵的大小。空间复杂度 ，用于存储每个子矩阵的元素。
class Solution:
def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
m, n = len(grid), len(grid[0])
ans = [[0] * (n - k + 1) for _ in range(m - k + 1)]
for i in range(m - k + 1):
for j in range(n - k + 1):
nums = []
for x in range(i, i + k):
for y in range(j, j + k):
nums.append(grid[x][y])
nums.sort()
d = min((abs(a - b) for a, b in pairwise(nums) if a != b), default=0)
ans[i][j] = d
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a deep understanding of sorting and array manipulation.
- question_mark
Watch for clear communication on trade-offs between brute-force and optimized solutions.
- question_mark
Ensure the candidate can discuss sliding window techniques and their efficiency.
常见陷阱
外企场景- error
Overlooking the overlap of values in sliding windows and recalculating from scratch.
- error
Not properly handling edge cases such as submatrices that span the entire grid.
- error
Misunderstanding the relationship between grid size and the required output size.
进阶变体
外企场景- arrow_right_alt
Consider variations with larger k values or non-square matrices.
- arrow_right_alt
What if the grid contains duplicate values? How does that affect the calculation?
- arrow_right_alt
Explore different data structures for optimizing the search for minimum differences.