Leetcode 1292. 元素和小于等于阈值的正方形的最大边长 - Maximum Side Length Of A Square With Sum Less Than Or Equal To Threshold

目录

1. 二分搜索
2. 枚举

题目链接

官方题解提供了两种方法，而且也有详细解释

两个方法的共同的地方是使用前缀数组以 O（1） 时间求任意矩形内元素和。（正方形也是矩形，但这里前缀数组不仅可以求正方形）

第一个方法二分的是正方形的边长，官方题解里说如果直接迭代找会超时。

第二个方法是对迭代的优化，思路就是每次都从当前找到的最大正方形边长开始迭代。

二分搜索

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        n, m = len(mat), len(mat[0])
        P = [[0] * (m+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1]
        l, r = 0, min(m,n)
        ans = 0
        def get_sum(x1, y1, x2, y2):
            return P[x2][y2] + P[x1][y1] - P[x1][y2] - P[x2][y1]
        while l <= r:
            mid = (l+r) >> 1
            find = any(get_sum(i, j, i+mid, j+mid)<=threshold for i in range(0, n-mid+1) for j in range(0, m-mid+1))
            if find:
                ans = max(ans, mid)
                l = mid+1
            else:
                r = mid-1
        return ans

枚举

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        n, m = len(mat), len(mat[0])
        P = [[0] * (m+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + mat[i-1][j-1]
        ans = 0
        #for p in P: print(p)
        def get_sum(x1, y1, x2, y2):
            return P[x2][y2] + P[x1][y1] - P[x1][y2] - P[x2][y1]
        i = 0
        while i < n - ans:
            j = 0
            while j < m - ans:
                k = ans + 1
                while i + k <= n and j + k <= m:
                    if get_sum(i, j, i+k, j+k) <= threshold:
                        ans = k
                    else:
                        break
                    k += 1
                j += 1
            i += 1
        return ans