class Solution(object):def maxSideLength(self, mat, threshold):""":type mat: List[List[int]]:type threshold: int:rtype: int"""start=0end=min(len(mat),len(mat[0]))s=starte=end# 二维前缀和# sum=sum[len(mat)+1][len(mat[0])+1]rows, cols = len(mat), len(mat[0])sum = [[0] * (cols + 1) for _ in range(rows + 1)]for i in range(1,len(mat)+1):for j in range(1,len(mat[0])+1):sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+mat[i-1][j-1]def valid(mid):# if mid==0:# return Falsefor i in range(mid,rows+1):for j in range(mid,cols+1):cursum=sum[i][j]-sum[i-mid][j]-sum[i][j-mid]+sum[i-mid][j-mid]if cursum<=threshold:return Truereturn Falsemaxx=0while s<=e:mid=s+(e-s)//2if valid(mid):maxx=mids=mid+1else:e=mid-1return maxx
1 判断用二维前缀和矩阵
2 求max 用另一个数保存
