LeetCode 3567.子矩阵的最小绝对差题目描述给定一个m x n的整数矩阵grid和一个整数k需要找出所有大小为k x k的子网格并计算每个子网格内不同元素之间的最小绝对差。示例输入grid[[1,2,3],[4,5,6],[7,8,9]],k2输出[[1,1],[1,1]]解释所有2x2子网格的相邻不同元素的最小差值都是1解法一暴力枚举基础解法思路分析最直观的思路是遍历所有可能的k x k子网格提取子网格中的所有元素对元素进行排序遍历排序后的数组找出相邻元素的最小差值代码实现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;// 提取当前k x k子网格的所有元素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;}};复杂度分析时间复杂度O(m × n × k² log k)子网格数量O(m × n)每个子网格排序O(k² log k)空间复杂度O(k²)优缺点✅优点实现简单思路清晰❌缺点效率较低存在大量重复计算解法二滑动窗口优化优化思路观察发现相邻子网格之间存在大量重叠元素。我们可以利用这个特性使用滑动窗口和有序数据结构来避免重复排序。核心思想使用multiset维护当前窗口的所有元素向右滑动时移除左边界元素添加右边界元素每次滑动后只需重新计算最小差值无需完全重排序代码实现classSolution{public:vectorvectorintminAbsDiff(vectorvectorintgrid,intk){intmgrid.size(),ngrid[0].size();vectorans(m-k1,vectorint(n-k1));for(inti0;im-k;i){// 使用multiset维护当前窗口的所有元素multisetintwindow;// 初始化第一列窗口for(intx0;xk;x){for(inty0;yk;y){window.insert(grid[ix][y]);}}// 计算第一个窗口的最小差值ans[i][0]getMinDiff(window);// 向右滑动窗口for(intj1;jn-k;j){// 移除左边界元素for(intx0;xk;x){autoitwindow.find(grid[ix][j-1]);window.erase(it);}// 添加右边界元素for(intx0;xk;x){window.insert(grid[ix][jk-1]);}// 计算新的最小差值ans[i][j]getMinDiff(window);}}returnans;}private:// 计算有序集合的最小差值intgetMinDiff(multisetintwindow){intresINT_MAX;autoitwindow.begin();intprev*it;for(it;it!window.end();it){if(*itprev){resmin(res,*it-prev);}prev*it;}returnres;}};复杂度分析时间复杂度O(m × n × k log k)每个子网格的更新操作O(k log k)空间复杂度O(m × n k²)解法三桶排序优化适用于小数值范围优化思路如果题目给定的数值范围较小例如 0-1000可以使用计数排序的思想将时间复杂度从 O(k² log k) 降到 O(k² V)其中 V 是数值范围。代码实现classSolution{public:vectorvectorintminAbsDiff(vectorvectorintgrid,intk){intmgrid.size(),ngrid[0].size();constintMAX_VAL1000;// 根据题目给定的数值范围调整vectorans(m-k1,vectorint(n-k1));for(inti0;im-k;i){for(intj0;jn-k;j){vectorintfreq(MAX_VAL1,0);// 统计频率for(intx0;xk;x){for(inty0;yk;y){freq[grid[ix][jy]];}}// 查找最小差值intresINT_MAX;intprev-1;for(intval0;valMAX_VAL;val){if(freq[val]0){if(prev!-1){resmin(res,val-prev);}prevval;}}ans[i][j]res;}}returnans;}};复杂度分析时间复杂度O(m × n × (k² V))其中 V 是数值范围空间复杂度O(V)适用场景✅ 数值范围较小的题目❌ 数值范围大时会浪费大量空间和时间性能对比总结解法时间复杂度空间复杂度优点缺点暴力枚举O(mn × k² log k)O(k²)实现简单效率低滑动窗口O(mn × k log k)O(mn k²)效率高通用性强实现较复杂桶排序O(mn × (k² V))O(V)数值范围小时极快受数值范围限制
LeetCode 3567.子矩阵的最小绝对差
LeetCode 3567.子矩阵的最小绝对差题目描述给定一个m x n的整数矩阵grid和一个整数k需要找出所有大小为k x k的子网格并计算每个子网格内不同元素之间的最小绝对差。示例输入grid[[1,2,3],[4,5,6],[7,8,9]],k2输出[[1,1],[1,1]]解释所有2x2子网格的相邻不同元素的最小差值都是1解法一暴力枚举基础解法思路分析最直观的思路是遍历所有可能的k x k子网格提取子网格中的所有元素对元素进行排序遍历排序后的数组找出相邻元素的最小差值代码实现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;// 提取当前k x k子网格的所有元素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;}};复杂度分析时间复杂度O(m × n × k² log k)子网格数量O(m × n)每个子网格排序O(k² log k)空间复杂度O(k²)优缺点✅优点实现简单思路清晰❌缺点效率较低存在大量重复计算解法二滑动窗口优化优化思路观察发现相邻子网格之间存在大量重叠元素。我们可以利用这个特性使用滑动窗口和有序数据结构来避免重复排序。核心思想使用multiset维护当前窗口的所有元素向右滑动时移除左边界元素添加右边界元素每次滑动后只需重新计算最小差值无需完全重排序代码实现classSolution{public:vectorvectorintminAbsDiff(vectorvectorintgrid,intk){intmgrid.size(),ngrid[0].size();vectorans(m-k1,vectorint(n-k1));for(inti0;im-k;i){// 使用multiset维护当前窗口的所有元素multisetintwindow;// 初始化第一列窗口for(intx0;xk;x){for(inty0;yk;y){window.insert(grid[ix][y]);}}// 计算第一个窗口的最小差值ans[i][0]getMinDiff(window);// 向右滑动窗口for(intj1;jn-k;j){// 移除左边界元素for(intx0;xk;x){autoitwindow.find(grid[ix][j-1]);window.erase(it);}// 添加右边界元素for(intx0;xk;x){window.insert(grid[ix][jk-1]);}// 计算新的最小差值ans[i][j]getMinDiff(window);}}returnans;}private:// 计算有序集合的最小差值intgetMinDiff(multisetintwindow){intresINT_MAX;autoitwindow.begin();intprev*it;for(it;it!window.end();it){if(*itprev){resmin(res,*it-prev);}prev*it;}returnres;}};复杂度分析时间复杂度O(m × n × k log k)每个子网格的更新操作O(k log k)空间复杂度O(m × n k²)解法三桶排序优化适用于小数值范围优化思路如果题目给定的数值范围较小例如 0-1000可以使用计数排序的思想将时间复杂度从 O(k² log k) 降到 O(k² V)其中 V 是数值范围。代码实现classSolution{public:vectorvectorintminAbsDiff(vectorvectorintgrid,intk){intmgrid.size(),ngrid[0].size();constintMAX_VAL1000;// 根据题目给定的数值范围调整vectorans(m-k1,vectorint(n-k1));for(inti0;im-k;i){for(intj0;jn-k;j){vectorintfreq(MAX_VAL1,0);// 统计频率for(intx0;xk;x){for(inty0;yk;y){freq[grid[ix][jy]];}}// 查找最小差值intresINT_MAX;intprev-1;for(intval0;valMAX_VAL;val){if(freq[val]0){if(prev!-1){resmin(res,val-prev);}prevval;}}ans[i][j]res;}}returnans;}};复杂度分析时间复杂度O(m × n × (k² V))其中 V 是数值范围空间复杂度O(V)适用场景✅ 数值范围较小的题目❌ 数值范围大时会浪费大量空间和时间性能对比总结解法时间复杂度空间复杂度优点缺点暴力枚举O(mn × k² log k)O(k²)实现简单效率低滑动窗口O(mn × k log k)O(mn k²)效率高通用性强实现较复杂桶排序O(mn × (k² V))O(V)数值范围小时极快受数值范围限制
