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(mn)$，内层ans总时间复杂度不会超过$O\min(m,n)$。

• 时间复杂度$O(mn)$
• 空间复杂度$O(N\log N)$

AC代码

C++

/*
 * @LastEditTime: 2026-01-19 21:55:16
 */
class Solution {
public:
    int maxSideLength(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;
    }
};

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

千篇源码题解已开源