Medium

题目描述

给你一个 m x n 的整数矩阵 grid 和一个整数 k。

对于 grid 中每个连续的 k x k 子矩阵，计算该子矩阵内任意两个不同值之间的最小绝对差值。

返回一个大小为 (m - k + 1) x (n - k + 1) 的二维数组 ans，其中 ans[i][j] 是以 (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
  • -10^5 <= grid[i][j] <= 10^5
  • 1 <= k <= min(m, n)

解题思路

这是一道滑动窗口和排序的综合题目。核心思路是暴力枚举每个 k×k 子矩阵，然后计算其中的最小绝对差值。

解题步骤：

  1. 遍历所有可能的 k×k 子矩阵的左上角位置 (i, j)
  2. 对于每个子矩阵，收集其中所有元素到一个数组中
  3. 对数组进行排序，这样相邻元素的差值就是候选答案
  4. 遍历排序后的数组，找到相邻元素的最小差值
  5. 如果数组中只有一个唯一元素，返回 0

时间复杂度优化考虑： 虽然题目提示使用暴力方法，但我们可以通过排序来高效计算最小差值。对于每个 k×k 子矩阵，我们需要 O(k²) 时间收集元素，O(k²log(k²)) 时间排序，O(k²) 时间找最小差值。

边界情况处理：

  • 当 k=1 时，每个子矩阵只有一个元素，最小差值为 0
  • 当子矩阵中所有元素相同时，最小差值为 0
  • 只有两个不同元素时，差值就是它们的绝对差

这种方法虽然是暴力解法，但在给定的约束条件下（矩阵大小最大 30×30）是完全可行的。

代码实现

class Solution {
public:
    vector<vector<int>> minAbsDiff(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> ans(m - k + 1, vector<int>(n - k + 1));
        
        for (int i = 0; i <= m - k; i++) {
            for (int j = 0; j <= n - k; j++) {
                vector<int> values;
                for (int x = i; x < i + k; x++) {
                    for (int y = j; y < j + k; y++) {
                        values.push_back(grid[x][y]);
                    }
                }
                
                sort(values.begin(), values.end());
                
                int minDiff = INT_MAX;
                for (int idx = 1; idx < values.size(); idx++) {
                    if (values[idx] != values[idx - 1]) {
                        minDiff = min(minDiff, values[idx] - values[idx - 1]);
                    }
                }
                
                ans[i][j] = (minDiff == INT_MAX) ? 0 : minDiff;
            }
        }
        
        return ans;
    }
};

class Solution:
    def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        ans = []
        
        for i in range(m - k + 1):
            row = []
            for j in range(n - k + 1):
                values = []
                for x in range(i, i + k):
                    for y in range(j, j + k):
                        values.append(grid[x][y])
                
                values.sort()
                
                min_diff = float('inf')
                for idx in range(1, len(values)):
                    if values[idx] != values[idx - 1]:
                        min_diff = min(min_diff, values[idx] - values[idx - 1])
                
                row.append(0 if min_diff == float('inf') else min_diff)
            ans.append(row)
        
        return ans

public class Solution {
    public int[][] MinAbsDiff(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        int[][] ans = new int[m - k + 1][];
        
        for (int i = 0; i <= m - k; i++) {
            ans[i] = new int[n - k + 1];
            for (int j = 0; j <= n - k; j++) {
                List<int> values = new List<int>();
                for (int x = i; x < i + k; x++) {
                    for (int y = j; y < j + k; y++) {
                        values.Add(grid[x][y]);
                    }
                }
                
                values.Sort();
                
                int minDiff = int.MaxValue;
                for (int idx = 1; idx < values.Count; idx++) {
                    if (values[idx] != values[idx - 1]) {
                        minDiff = Math.Min(minDiff, values[idx] - values[idx - 1]);
                    }
                }
                
                ans[i][j] = (minDiff == int.MaxValue) ? 0 : minDiff;
            }
        }
        
        return ans;
    }
}

var minAbsDiff = function(grid, k) {
    const m = grid.length;
    const n = grid[0].length;
    const ans = [];
    
    for (let i = 0; i <= m - k; i++) {
        const row = [];
        for (let j = 0; j <= n - k; j++) {
            const values = [];
            for (let x = i; x < i + k; x++) {
                for (let y = j; y < j + k; y++) {
                    values.push(grid[x][y]);
                }
            }
            
            const uniqueValues = [...new Set(values)].sort((a, b) => a - b);
            
            if (uniqueValues.length === 1) {
                row.push(0);
            } else {
                let minDiff = Infinity;
                for (let p = 0; p < uniqueValues.length - 1; p++) {
                    minDiff = Math.min(minDiff, uniqueValues[p + 1] - uniqueValues[p]);
                }
                row.push(minDiff);
            }
        }
        ans.push(row);
    }
    
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O((m-k+1)(n-k+1) × k² × log(k²))
空间复杂度O(k²)

详细分析：

  • 外层循环遍历所有可能的子矩阵位置：O((m-k+1)(n-k+1))
  • 对于每个子矩阵，收集k²个元素：O(k²)
  • 对k²个元素进行排序：O(k²log(k²))
  • 遍历排序后数组找最小差值：O(k²)
  • 空间复杂度主要来自存储每个子矩阵元素的临时数组：O(k²)