题目

给你一个大小为 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

解题思路

目标：在一个 $M \times N$ 的矩阵中，找到一个边长为 $k$ 的正方形，使得其元素和 $\le$ threshold，求最大的 $k$。

如果使用最直觉的暴力解法：

1. 枚举所有可能的边长 $k$ ($1 \to \min(M,N)$)。
2. 枚举所有可能的左上角坐标 $(i, j)$。
3. 计算这个 $k \times k$ 正方形里的元素和。

瓶颈在哪里？

第 3 步是最大的瓶颈。每次计算一个区域和，都要遍历 $k^2$ 个元素。

总时间复杂度会达到 $O(M \cdot N \cdot \min(M,N)^3)$。

对于 $300 \times 300$ 的数据，这绝对会超时。

结论：我们需要一种能在 $O(1)$ 时间内算出任意子矩阵和的方法。

为了解决求和慢的问题，我们引入二维前缀和 (2D Prefix Sum)。这是处理矩阵区域和问题的标准“起手式”。

1. 定义

P[i][j] 表示从矩阵左上角 (0, 0) 到位置 (i-1, j-1) （即前 $i$ 行、前 $j$ 列）的矩形区域内所有元素的和。

(注意：为了处理边界方便，P 数组通常比原矩阵多一行一列，下标从 1 开始)

2. 构建公式 (递推)

如何快速填满 P 数组？利用容斥原理：

$$P[i][j] = \underbrace{P[i-1][j]}{\text{上部分}} + \underbrace{P[i][j-1]}{\text{左部分}} - \underbrace{P[i-1][j-1]}{\text{重复减去的左上角}} + \underbrace{mat[i-1][j-1]}{\text{当前元素}}$$

3. 查询公式 ($O(1)$ 求和)

有了 P 数组，计算任意正方形（右下角为 $r, c$，边长为 $k$）的和：

$$Sum = P[r][c] - P[r-k][c] - P[r][c-k] + P[r-k][c-k]$$

这一步完成后，求和操作从 $O(k^2)$ 降维到了 $O(1)$。

现在我们能快速求和了，剩下的问题是怎么找最大的 $k$。这里有两条技术路线，也是面试中展示思维深度的关键。

路线 A：二分查找 (常规解法)

思路：

正方形边长具有单调性。

• 如果边长 $k$ 满足条件（和 $\le$ 阈值），那么 $k-1$ 一定也满足（因为元素非负）。
• 如果边长 $k$ 不满足，那么 $k+1$ 肯定也不满足。

算法：

1. 二分枚举边长 $k$ (范围 $0 \to \min(M,N)$)。
2. check(k) 函数：遍历矩阵所有位置，看是否存在一个边长为 $k$ 的正方形满足条件。
3. 时间复杂度：$O(M \cdot N \cdot \log(\min(M,N)))$。
   • 这是完全可以接受的解法。

路线 B：贪心/智能枚举 (最优解法 $O(MN)$)

核心逻辑：

我们不需要对每个位置都重新测试“它能容纳的最大边长是多少”。我们只关心全局最大值是否能被刷新。

类比“跳高比赛”：

• 我们维护一个全局最高纪录 ans（假设当前是 3 米）。
• 当遍历到下一个位置（下一个运动员）时，我们不让他从 1 米开始跳，而是直接问：“你能跳过 4 米 (ans + 1) 吗？”
  • 能：太棒了，世界纪录刷新，ans 变成 4。
  • 不能：无所谓，我们不关心他到底能跳 2 米还是 3 米，因为那对刷新纪录没帮助。我们带着 ans = 3 继续看下一个人。

代码执行流重现：

1. 初始化 ans = 0 (或者 1)。
2. 遍历矩阵的每一个位置 (r, c) 作为正方形的右下角。
3. 只检查：以 (r, c) 为右下角，边长为 ans + 1 的正方形。
   • 检查1 (边界)：r 和 c 够大吗？(比如 ans+1 是 5，你坐标才 (3,3)，那肯定放不下)。
   • 检查2 (数值)：这个区域的和 $\le$ threshold 吗？
4. 如果上述两个都满足：说明我们找到了一个更大的正方形，ans++。
5. 如果不满足：ans 不变，继续下一个位置。

复杂度分析

时间复杂度 (Time Complexity)

总复杂度：$O(M \cdot N)$

我们可以将代码拆解为两个主要部分：

• 部分 A：预处理（构建前缀和数组）
  • 我们需要遍历整个矩阵一次来填充 prefix 数组。
  • 对于矩阵中的每个位置 $(i, j)$，执行的计算是加减法，耗时 $O(1)$。
  • 这一步的复杂度是 $O(M \cdot N)$。
• 部分 B：贪心枚举（查找最大边长）
  • 这是一个双重循环：外层遍历行 ($1 \dots M$)，内层遍历列 ($1 \dots N$)。
  • 总共迭代次数是 $M \cdot N$ 次。
  • 循环内部的操作：
    1. testLen = ans + 1 (加法，$O(1)$)
    2. 边界检查 row >= testLen ($O(1)$)
    3. getSum 函数调用 (4次数组访问 + 3次加减法，$O(1)$)
    4. ans++ ($O(1)$)
  • 虽然我们在寻找最大值，但 ans 变量在整个过程中只增不减。内部没有额外的循环（不像暴力法那样还要遍历边长）。
  • 这一步的复杂度也是 $O(M \cdot N)$。

结论：

$$O(M \cdot N) + O(M \cdot N) = O(M \cdot N)$$

这是该问题的理论下界（Lower Bound）。因为要解决这个问题，你至少需要读取输入矩阵中的每一个元素一次，所以不可能有优于 $O(MN)$ 的算法。

空间复杂度 (Space Complexity)

总复杂度：$O(M \cdot N)$

• 辅助空间：我们需要一个大小为 $(M+1) \times (N+1)$ 的整数数组 prefix 来存储前缀和。
• 占用内存：假设 $M, N = 300$，int 为 4 字节。
  • $300 \times 300 \times 4 \text{ Bytes} \approx 360 \text{ KB}$。
  • 这在算法竞赛或工程中都是非常小的开销。

进阶优化（In-place Optimization，仅供参考）：

如果不允许使用额外空间（且允许修改原数组 mat），我们可以直接在 mat 上计算前缀和。

$$mat[i][j] \leftarrow mat[i][j] + mat[i-1][j] + \dots$$

这样空间复杂度可以降为 $O(1)$（不计算输入本身的空间）。但在实际工程中，为了保持数据不可变性（Immutability），通常不建议这么做，除非内存极其紧张。

具体代码

func maxSideLength(mat [][]int, threshold int) int {

    m := len(mat)
    n := len(mat[0])
    prefix := make([][]int, m + 1)
    for i := range prefix {
        prefix[i] = make([]int, n + 1)
    }
    
    minNum := 10000
    for i := 1; i < m + 1; i++ {
        for j := 1; j < n + 1; j++ {
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + mat[i - 1][j - 1]
            minNum = min(minNum, mat[i - 1][j - 1])
        }
    }

    if minNum > threshold {
        return 0
    }

    getSum := func(i ,j, length int) int {
        return prefix[i][j] - prefix[i - length][j] - prefix[i][j - length] + prefix[i - length][j - length]
    }

    ans := 1
    for row := 1; row < m + 1; row++ {
        for col := 1; col < n + 1; col++ {
            testLen := ans + 1
            if row - testLen >= 0 && col - testLen >= 0 {
                if getSum(row, col, testLen) <= threshold {
                    ans++
                }
            }
        }
    }

    return ans
}