1292. 元素和小于等于阈值的正方形的最大边长

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def square_sum(self,pre,x1,y1,x2,y2):
        return pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m,n = len(mat),len(mat[0])
        # 构建一个辅助 数组： 它的右下大部分区域 就是 二维前缀和数组。
        pre = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                pre[i][j] = mat[i-1][j-1]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]
        # 用二分法找 适合的边长，（枚举某一边长的所有可能性,看是否合法）。
        l,r = 1,min(n,m)
        while l<=r:
            mid = (l+r)>>1
            judge ='!ok'
            # i，j 正方形区域的左上角索引,记得i对应m。枚举就是枚举左上角可能出现的所有位置。
            for i in range(1,m-mid+1+1):
                for j in range(1,n-mid+1+1):
                    if self.square_sum(pre,i,j,i+mid-1,j+mid-1)<=threshold:
                        judge = 'ok'
            if judge=='ok':
                print('%d is ok'%mid)
                l = mid+1
            else:
                r = mid-1
        return r 

        # 其实二分法 用了一个暴力枚举在里面，还能继续在枚举的方法上改进！！！