企业官网建设流程全解析

湛江专业做网站,模板网站代理,百度收录查询api,金坛网站建设价格【LetMeFly】1292.元素和小于等于阈值的正方形的最大边长#xff1a;二维前缀和#xff08;无需二分#xff09;抽象速懂的描述 力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/ 给你一…【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.lengthn mat[i].length1 m, n 3000 mat[i][j] 1040 threshold 105解题方法前缀和二维矩阵的二维前缀和可以快速计算出某个子矩阵的元素和。AB CD其中prefix[D]代表从左上角到D这个矩阵的元素和计算方法为DBC-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(vectorvectorintmat,intthreshold){intnmat.size(),mmat[0].size();vectorvectorintprefix(n1,vectorint(m1));for(inti0;in;i){for(intj0;jm;j){prefix[i1][j1]mat[i][j]-prefix[i][j]prefix[i][j1]prefix[i1][j];}}intans0;for(inti0;in;i){for(intj0;jm;j){while(iansnjansmprefix[ians1][jans1]-prefix[ians1][j]-prefix[i][jans1]prefix[i][j]threshold){ans;}}}returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源