🔲 初学者友好指南 “Maximum Side Length of a Square” – LeetCode 1292 (C++, Python, JavaScript)

Source: Dev.to

问题概述

给定

• 一个名为 mat 的二维整数矩阵。
• 一个整数 threshold。

目标

返回一个正方形子矩阵的最大边长，使得该子矩阵中所有元素的和 ≤ 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

• 边长 1 → 任意单个 1 都可。
• 边长 2 → 左上角的方阵 [[1,1],[1,1]] 和为 4 → 有效。
• 边长 3 → 最小的 3×3 方阵已经超过 4。

输出

2

示例 2

输入

mat = [
  [2,2,2,2,2],
  [2,2,2,2,2],
  ...
]
threshold = 1

每个元素都是 2，因此即使是 1×1 方阵也超过阈值。

输出

0

直觉

为高效求解，我们结合两种强大的技术：

1. 二维前缀和 – 预处理矩阵，使任意正方形的和能够在 O(1) 时间内获得。
2. 答案二分查找 – 边长具有单调性：如果大小为 k 的正方形可行，则任意更小的尺寸也可行。利用此特性可以在 O(log min(m,n)) 时间内找到最大的合法 k。

1️⃣ 二维前缀和

preSum[i][j] 保存从左上角 (0,0) 到 (i‑1, j‑1)（含）的矩形和。

侧长为 len、右下角坐标为 (i, j) 的正方形的和为：

sum = preSum[i][j]
      - preSum[i‑len][j]
      - preSum[i][j‑len]
      + preSum[i‑len][j‑len]

preSum 表中的所有索引均为 1‑基，因此该公式在 O(1) 时间内生效。

2️⃣ 二分查找答案

• Low = 0，High = min(rows, cols)。
• 当 low ≤ high 时：
  • mid = (low + high) // 2。
  • 使用前缀和检查是否存在任意 mid × mid 正方形，使其和 ≤ threshold。
  • 若 找到，记录 mid 为候选值并搜索更大的尺寸（low = mid + 1）。
  • 否则，搜索更小的尺寸（high = mid - 1）。

整体复杂度为 O(m·n + m·n·log min(m,n))，主要耗时在前缀和的构建以及二分查找过程中的检查。

代码块

C++（部分）

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> preSum(m + 1, vector<int>(n + 1, 0));

        // Build 2‑D Prefix Sum
        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];
            }
        }
        // ... (rest of the algorithm)
    }
};

Python（部分）

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)]

        # Build 2‑D Prefix Sum
        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: int) -> bool:
            if k == 0:
                return True
            for i in range(k, m + 1):
                for j in range(k, n + 1):
                    cur = (preSum[i][j] -
                           preSum[i - k][j] -
                           preSum[i][j - k] +
                           preSum[i - k][j - k])
                    if cur <= threshold:
                        return True
            return False

        # Binary search omitted for brevity

JavaScript（部分）

var maxSideLength = function(mat, threshold) {
    const m = mat.length, n = mat[0].length;
    const preSum = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

    // Build 2‑D Prefix Sum
    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];
        }
    }

    const canFit = (k) => {
        if (k === 0) return true;
        for (let i = k; i <= m; ++i) {
            for (let j = k; j <= n; ++j) {
                const cur = preSum[i][j] - preSum[i - k][j] - preSum[i][j - k] + preSum[i - k][j - k];
                if (cur <= threshold) return true;
            }
        }
        return false;
    };

    // Binary search omitted for brevity
};

清理后的 JavaScript 实现

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];
    }
}

let low = 0;
let high = Math.min(m, n);
let ans = 0;

while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (mid === 0) {
        low = mid + 1;
        continue;
    }

    let found = false;
    for (let i = mid; i <= m; i++) {
        for (let j = mid; j <= n; j++) {
            let currentSum = preSum[i][j] - preSum[i - mid][j] -
                             preSum[i][j - mid] + preSum[i - mid][j - mid];
            if (currentSum <= threshold) {
                found = true;
                break;
            }
        }
        if (found) break;
    }

    if (found) {
        ans = mid;
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
return ans;

关键要点

• 二维前缀和： 该技术在预处理后将区域求和查询从 O(k²) 降低到 O(1)。它是网格类问题的必备技巧。
• 结果的二分搜索： 当需要找到满足条件的“最大”或“最小”值时，考虑搜索空间是否有序，并使用二分搜索。
• 容斥原理： 前缀和与区域和的公式直接应用了该原理，确保不会对重叠区域进行重复计数。

最后思考

这个问题是一个绝佳的例子，展示了将两个相对简单的概念结合起来如何能够得到高度优化的解决方案。在实际应用中，这类空间查询被用于 Computer Vision 中的目标检测，以及 Geographic Information Systems (GIS) 中用于分析特定地图区域内的数据密度。掌握 2D 前缀和将在任何涉及矩阵操作的面试中为你提供显著优势。