M3567.子矩阵的最小绝对差

brute force, https://leetcode.cn/problems/minimum-absolute-difference-in-sliding-submatrix/

给你一个 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 <= 30
1 <= n == grid[i].length <= 30
-105 <= grid[i][j] <= 10^5
1 <= k <= min(m, n)

遍历每一个 k x k 子矩阵，并为每个子矩阵计算不同元素之间的最小绝对差：

python

from typing import List

class Solution:
    def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        res = []

        for i in range(m - k + 1):
            row = []
            for j in range(n - k + 1):
                # 收集 k x k 子矩阵内所有元素
                elements = []
                for x in range(i, i + k):
                    for y in range(j, j + k):
                        elements.append(grid[x][y])
                
                # 去重并排序
                unique_sorted = sorted(set(elements))

                # 如果只有一个元素或所有元素相同，最小差为 0
                if len(unique_sorted) <= 1:
                    row.append(0)
                else:
                    # 计算最小绝对差
                    min_diff = float('inf')
                    for a in range(1, len(unique_sorted)):
                        min_diff = min(min_diff, abs(unique_sorted[a] - unique_sorted[a - 1]))
                    row.append(min_diff)
            res.append(row)
        
        return res

✅ 解释

每个 k x k 子矩阵都通过双重循环来提取元素。
使用 set 去重，sorted 排序后，相邻元素之间的差值就是可能的最小差值候选。
时间复杂度为：
- 最多 (m - k + 1) * (n - k + 1) 次子矩阵处理。
- 每次子矩阵最多处理 k^2 个元素，排序为 O(k^2 log k)。
- 所以总时间复杂度是 O((m-k+1)(n-k+1) * k^2 log k)，在 m, n 最大为 30 时是可以接受的。

M3567.子矩阵的最小绝对差 ​

M3567.子矩阵的最小绝对差