LeetCode 1292.元素和小于等于阈值的正方形的最大边长：二维前缀和（无需二分）+抽象速懂的描述

【LetMeFly】1292.元素和小于等于阈值的正方形的最大边长：二维前缀和（无需二分）+抽象速懂的描述

力扣题目链接：https://leetcode.cn/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。
 

示例 1：

输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 输出：2 解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。

示例 2：

输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 输出：0

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 104
• 0 <= threshold <= 105 

解题方法：前缀和

二维矩阵的二维前缀和可以快速计算出某个子矩阵的元素和。

AB CD 

其中prefix[D]代表从左上角到D这个矩阵的元素和，计算方法为D+B+C-A。

ABC DEF GHI 

那么想计算EFHI这个子矩阵的元素和就只需要prefix[I]-prefix[C]-prefix[G]+prefix[A]。

二层循环枚举矩阵左上角顶点，使用一个变量ans作为答案合法边长并且只增不减，那么二层循环时间复杂度 O ( m n ) O(mn) O(mn)，内层ans总时间复杂度不会超过 O min ⁡ ( m , n ) O\min(m,n) Omin(m,n)。

• 时间复杂度 O ( m n ) O(mn) O(mn)
• 空间复杂度 O ( N log ⁡ N ) O(N\log N) O(NlogN)

AC代码

C++

/* * @LastEditTime: 2026-01-19 21:55:16 */classSolution{public:intmaxSideLength(vector<vector<int>>& mat,int threshold){int n = mat.size(), m = mat[0].size(); vector<vector<int>>prefix(n +1,vector<int>(m +1));for(int i =0; i < n; i++){for(int j =0; j < m; j++){ prefix[i +1][j +1]= mat[i][j]- prefix[i][j]+ prefix[i][j +1]+ prefix[i +1][j];}}int ans =0;for(int i =0; i < n; i++){for(int j =0; j < m; j++){while(i + ans < n && j + ans < m && prefix[i + ans +1][j + ans +1]- prefix[i + ans +1][j]- prefix[i][j + ans +1]+ prefix[i][j]<= threshold){ ans++;}}}return ans;}};

同步发文于ZEEKLOG和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源