LeetCode 3567. 子矩阵的最小绝对差【暴力枚举】中等

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

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

解法 暴力枚举

暴力枚举所有子矩形，把子矩形中的所有元素添加到一个数组a aa中，然后把a aa排序。排序后，不同元素之差的最小值一定来自a aa的相邻元素，计算相邻不同元素之差的最小值。

classSolution{publicint[][]minAbsDiff(int[][]grid,intk){intm=grid.length;intn=grid[0].length;int[][]ans=newint[m-k+1][n-k+1];int[]a=newint[k*k];for(inti=0;i<=m-k;i++){for(intj=0;j<=n-k;j++){intidx=0;for(intx=0;x<k;x++){for(inty=0;y<k;y++){a[idx++]=grid[i+x][j+y];}}Arrays.sort(a);intres=Integer.MAX_VALUE;for(intp=1;p<a.length;p++){if(a[p]>a[p-1]){// 题目要求相减的两个数必须不同res=Math.min(res,a[p]-a[p-1]);}}if(res<Integer.MAX_VALUE){ans[i][j]=res;}}}returnans;}}

classSolution{public:vector<vector<int>>minAbsDiff(vector<vector<int>>&grid,intk){intm=grid.size(),n=grid[0].size();vectorans(m-k+1,vector<int>(n-k+1));for(inti=0;i<=m-k;i++){for(intj=0;j<=n-k;j++){vector<int>a;for(intx=0;x<k;x++){for(inty=0;y<k;y++){a.push_back(grid[i+x][j+y]);}}ranges::sort(a);intres=INT_MAX;for(intp=1;p<a.size();p++){if(a[p]>a[p-1]){// 题目要求相减的两个数必须不同res=min(res,a[p]-a[p-1]);}}if(res<INT_MAX){ans[i][j]=res;}}}returnans;}};

classSolution:defminAbsDiff(self,grid:List[List[int]],k:int)->List[List[int]]:m,n=len(grid),len(grid[0])ans=[[0]*(n-k+1)for_inrange(m-k+1)]foriinrange(m-k+1):sub_grid=grid[i:i+k]forjinrange(n-k+1):a=[]forrowinsub_grid:a+=row[j:j+k]a.sort()res=infforx,yinpairwise(a):ifx<y:# 题目要求相减的两个数必须不同res=min(res,y-x)ifres<inf:ans[i][j]=resreturnans

funcminAbsDiff(grid[][]int,kint)[][]int{m,n:=len(grid),len(grid[0])ans:=make([][]int,m-k+1)arr:=make([]int,k*k)fori:=rangeans{ans[i]=make([]int,n-k+1)forj:=rangeans[i]{a:=arr[:0]// 避免反复 makefor_,row:=rangegrid[i:i+k]{a=append(a,row[j:j+k]...)}slices.Sort(a)res:=math.MaxIntforp:=1;p<len(a);p++{ifa[p]>a[p-1]{// 题目要求相减的两个数必须不同res=min(res,a[p]-a[p-1])}}ifres<math.MaxInt{ans[i][j]=res}}}returnans}

复杂度分析：

• 时间复杂度：O ( ( m − k ) ( n − k ) k 2 log ⁡ k ) O( (m - k) (n - k) k^2 \log k)O((m−k)(n−k)k2logk)，其中m mm和n nn分别为g r i d gridgrid的行数和列数。
• 空间复杂度：O ( k 2 ) O(k^2)O(k2)。返回值不计入。

注：考虑用定长滑动窗口+有序集合+懒删除堆，用有序集合维护窗口（子矩阵）元素，用懒删除堆维护相邻不同元素之差。添加删除时更新相邻不同元素之差。这样可以做到O ( ( m − k ) n k log ⁡ k ) O( (m - k) nk \log k)O((m−k)nklogk)，但常数比较大。