Medium

题目描述

给你一个大小为 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] <= 10^4
  • 0 <= threshold <= 10^5

提示：

  • 将所有网格的前缀和存储在另一个二维数组中。
  • 尝试所有可能的解决方案，如果找不到就返回 0。
  • 如果 x 是一个有效答案，那么任何 y < x 也是有效答案。使用二分查找来找到答案。

解题思路

解题思路

这道题要求找到矩阵中元素和小于等于阈值的正方形的最大边长。

主要思路：

  1. 前缀和优化：由于需要频繁计算子矩阵的和，我们首先构建二维前缀和数组，这样可以在O(1)时间内计算任意子矩阵的和。

  2. 二分查找：题目提示了一个重要性质：如果边长为x的正方形满足条件，那么所有边长小于x的正方形也都满足条件。这种单调性让我们可以使用二分查找来优化时间复杂度。

  3. 验证函数：对于给定的边长k，我们需要检查是否存在至少一个边长为k的正方形，其元素和小于等于阈值。

算法步骤：

  1. 构建前缀和数组 preSum[i][j] 表示从 (0,0) 到 (i,j) 的矩形区域元素和
  2. 使用二分查找在 [0, min(m,n)] 范围内查找最大可能的边长
  3. 对于每个候选边长，遍历所有可能的正方形位置进行验证

时间复杂度优化：

  • 朴素做法：O(min(m,n) × m × n × k²)
  • 前缀和 + 暴力：O(min(m,n) × m × n)
  • 前缀和 + 二分查找：O(m × n + log(min(m,n)) × m × n)

代码实现

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size(), n = mat[0].size();
        
        // 构建前缀和数组
        vector<vector<int>> preSum(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i][j] = mat[i-1][j-1] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
            }
        }
        
        // 检查是否存在边长为k的正方形满足条件
        auto check = [&](int k) -> bool {
            for (int i = k; i <= m; i++) {
                for (int j = k; j <= n; j++) {
                    int sum = preSum[i][j] - preSum[i-k][j] - preSum[i][j-k] + preSum[i-k][j-k];
                    if (sum <= threshold) return true;
                }
            }
            return false;
        };
        
        // 二分查找最大边长
        int left = 0, right = min(m, n), ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return ans;
    }
};

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m, n = len(mat), len(mat[0])
        
        # 构建前缀和数组
        preSum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                preSum[i][j] = mat[i-1][j-1] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1]
        
        def check(k):
            """检查是否存在边长为k的正方形满足条件"""
            for i in range(k, m + 1):
                for j in range(k, n + 1):
                    sum_val = preSum[i][j] - preSum[i-k][j] - preSum[i][j-k] + preSum[i-k][j-k]
                    if sum_val <= threshold:
                        return True
            return False
        
        # 二分查找最大边长
        left, right, ans = 0, min(m, n), 0
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return ans

public class Solution {
    public int MaxSideLength(int[][] mat, int threshold) {
        int m = mat.Length, n = mat[0].Length;
        
        // 构建前缀和数组
        int[,] preSum = new int[m + 1, n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i, j] = mat[i-1][j-1] + preSum[i-1, j] + preSum[i, j-1] - preSum[i-1, j-1];
            }
        }
        
        // 检查是否存在边长为k的正方形满足条件
        bool Check(int k) {
            for (int i = k; i <= m; i++) {
                for (int j = k; j <= n; j++) {
                    int sum = preSum[i, j] - preSum[i-k, j] - preSum[i, j-k] + preSum[i-k, j-k];
                    if (sum <= threshold) return true;
                }
            }
            return false;
        }
        
        // 二分查找最大边长
        int left = 0, right = Math.Min(m, n), ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (Check(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return ans;
    }
}

var maxSideLength = function(mat, threshold) {
    const m = mat.length, n = mat[0].length;
    
    // 构建前缀和数组
    const preSum = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            preSum[i][j] = mat[i-1][j-1] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
        }
    }
    
    // 检查是否存在边长为k的正方形满足条件
    const check = (k) => {
        for (let i = k; i <= m; i++) {
            for (let j = k; j <= n; j++) {
                const sum = preSum[i][j] - preSum[i-k][j] - preSum[i][j-k] + preSum[i-k][j-k];
                if (sum <= threshold) return true;
            }
        }
        return false;
    };
    
    // 二分查找最大边长
    let left = 0, right = Math.min(m, n), ans = 0;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
前缀和 + 二分查找O(m × n + log(min(m,n)) × m × n)O(m × n)

时间复杂度说明：

  • 构建前缀和数组：O(m × n)
  • 二分查找：O(log(min(m,n)))
  • 每次验证：O(m × n)
  • 总时间复杂度：O(m × n + log(min(m,n)) × m × n)

空间复杂度说明：

  • 前缀和数组：O(m × n)
  • 其他辅助变量：O(1)