本文属于「征服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]],k2输出[[2]]解释只有一个可能的k x k子矩阵[[1, 8], [3, -2]]。子矩阵中的不同值为[1, 8, 3, -2]。子矩阵中的最小绝对差为|1 - 3| 2。因此答案为[[2]]。示例 2输入 grid[[3,-1]],k1输出[[0,0]]解释每个k x k子矩阵中只有一个不同的元素。因此答案为[[0, 0]]。示例 3输入 grid[[1,-2,3],[2,3,5]],k2输出[[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-10^5 grid[i][j] 10^51 k min(m, n)解法 暴力枚举暴力枚举所有子矩形把子矩形中的所有元素添加到一个数组a aa中然后把a aa排序。排序后不同元素之差的最小值一定来自a aa的相邻元素计算相邻不同元素之差的最小值。classSolution{publicint[][]minAbsDiff(int[][]grid,intk){intmgrid.length;intngrid[0].length;int[][]ansnewint[m-k1][n-k1];int[]anewint[k*k];for(inti0;im-k;i){for(intj0;jn-k;j){intidx0;for(intx0;xk;x){for(inty0;yk;y){a[idx]grid[ix][jy];}}Arrays.sort(a);intresInteger.MAX_VALUE;for(intp1;pa.length;p){if(a[p]a[p-1]){// 题目要求相减的两个数必须不同resMath.min(res,a[p]-a[p-1]);}}if(resInteger.MAX_VALUE){ans[i][j]res;}}}returnans;}}classSolution{public:vectorvectorintminAbsDiff(vectorvectorintgrid,intk){intmgrid.size(),ngrid[0].size();vectorans(m-k1,vectorint(n-k1));for(inti0;im-k;i){for(intj0;jn-k;j){vectorinta;for(intx0;xk;x){for(inty0;yk;y){a.push_back(grid[ix][jy]);}}ranges::sort(a);intresINT_MAX;for(intp1;pa.size();p){if(a[p]a[p-1]){// 题目要求相减的两个数必须不同resmin(res,a[p]-a[p-1]);}}if(resINT_MAX){ans[i][j]res;}}}returnans;}};classSolution:defminAbsDiff(self,grid:List[List[int]],k:int)-List[List[int]]:m,nlen(grid),len(grid[0])ans[[0]*(n-k1)for_inrange(m-k1)]foriinrange(m-k1):sub_gridgrid[i:ik]forjinrange(n-k1):a[]forrowinsub_grid:arow[j:jk]a.sort()resinfforx,yinpairwise(a):ifxy:# 题目要求相减的两个数必须不同resmin(res,y-x)ifresinf:ans[i][j]resreturnansfuncminAbsDiff(grid[][]int,kint)[][]int{m,n:len(grid),len(grid[0])ans:make([][]int,m-k1)arr:make([]int,k*k)fori:rangeans{ans[i]make([]int,n-k1)forj:rangeans[i]{a:arr[:0]// 避免反复 makefor_,row:rangegrid[i:ik]{aappend(a,row[j:jk]...)}slices.Sort(a)res:math.MaxIntforp:1;plen(a);p{ifa[p]a[p-1]{// 题目要求相减的两个数必须不同resmin(res,a[p]-a[p-1])}}ifresmath.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)但常数比较大。
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]],k2输出[[2]]解释只有一个可能的k x k子矩阵[[1, 8], [3, -2]]。子矩阵中的不同值为[1, 8, 3, -2]。子矩阵中的最小绝对差为|1 - 3| 2。因此答案为[[2]]。示例 2输入 grid[[3,-1]],k1输出[[0,0]]解释每个k x k子矩阵中只有一个不同的元素。因此答案为[[0, 0]]。示例 3输入 grid[[1,-2,3],[2,3,5]],k2输出[[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-10^5 grid[i][j] 10^51 k min(m, n)解法 暴力枚举暴力枚举所有子矩形把子矩形中的所有元素添加到一个数组a aa中然后把a aa排序。排序后不同元素之差的最小值一定来自a aa的相邻元素计算相邻不同元素之差的最小值。classSolution{publicint[][]minAbsDiff(int[][]grid,intk){intmgrid.length;intngrid[0].length;int[][]ansnewint[m-k1][n-k1];int[]anewint[k*k];for(inti0;im-k;i){for(intj0;jn-k;j){intidx0;for(intx0;xk;x){for(inty0;yk;y){a[idx]grid[ix][jy];}}Arrays.sort(a);intresInteger.MAX_VALUE;for(intp1;pa.length;p){if(a[p]a[p-1]){// 题目要求相减的两个数必须不同resMath.min(res,a[p]-a[p-1]);}}if(resInteger.MAX_VALUE){ans[i][j]res;}}}returnans;}}classSolution{public:vectorvectorintminAbsDiff(vectorvectorintgrid,intk){intmgrid.size(),ngrid[0].size();vectorans(m-k1,vectorint(n-k1));for(inti0;im-k;i){for(intj0;jn-k;j){vectorinta;for(intx0;xk;x){for(inty0;yk;y){a.push_back(grid[ix][jy]);}}ranges::sort(a);intresINT_MAX;for(intp1;pa.size();p){if(a[p]a[p-1]){// 题目要求相减的两个数必须不同resmin(res,a[p]-a[p-1]);}}if(resINT_MAX){ans[i][j]res;}}}returnans;}};classSolution:defminAbsDiff(self,grid:List[List[int]],k:int)-List[List[int]]:m,nlen(grid),len(grid[0])ans[[0]*(n-k1)for_inrange(m-k1)]foriinrange(m-k1):sub_gridgrid[i:ik]forjinrange(n-k1):a[]forrowinsub_grid:arow[j:jk]a.sort()resinfforx,yinpairwise(a):ifxy:# 题目要求相减的两个数必须不同resmin(res,y-x)ifresinf:ans[i][j]resreturnansfuncminAbsDiff(grid[][]int,kint)[][]int{m,n:len(grid),len(grid[0])ans:make([][]int,m-k1)arr:make([]int,k*k)fori:rangeans{ans[i]make([]int,n-k1)forj:rangeans[i]{a:arr[:0]// 避免反复 makefor_,row:rangegrid[i:ik]{aappend(a,row[j:jk]...)}slices.Sort(a)res:math.MaxIntforp:1;plen(a);p{ifa[p]a[p-1]{// 题目要求相减的两个数必须不同resmin(res,a[p]-a[p-1])}}ifresmath.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)但常数比较大。
