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,intthreshold){intn=mat.size(),m=mat[0].size();vector<vector<int>>prefix(n+1,vector<int>(m+1));for(inti=0;i<n;i++){for(intj=0;j<m;j++){prefix[i+1][j+1]=mat[i][j]-prefix[i][j]+prefix[i][j+1]+prefix[i+1][j];}}intans=0;for(inti=0;i<n;i++){for(intj=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++;}}}returnans;}};

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

千篇源码题解已开源