元素和小于等于阈值的正方形的最大边长 图解题解

框一个正方形让和不超阈值，返回的是边长还是面积

给一个 m×n 数字矩阵 mat 和阈值 threshold，要框一个正方形子区域（长宽相等），让框住的数之和不超过 threshold，取合格正方形里边长最大的，返回边长 k、不是面积 k×k。题面每行 1 1 3 2 4 3 2 的 3×7 矩阵、阈值 4，答案 2。

每验一个正方形都把格子重加一遍，重得离谱

正方形候选很多：每个左上角配一种边长就是一个，光左上角就 O(m·n) 个。若每验一个都把里面 k×k 个数逐个累加，单次求和 O(k²)，再套枚举左上角和边长，判定退化到 O(m·n·k²) 扫不动。慢在「求一块矩形的和」被一遍遍重算。

边长越大越难满足，这条单调让答案能二分

边长 k 能框出合格正方形，更小的 k-1 和更小、更易合格——边长越大越难满足。于是边长切成两段：小的可行、大的不可行，答案是可行段末位。单调就能二分：不直接算，猜一个边长用判定函数验证再往可行侧收，这叫二分答案。二分的是边长这个答案、不是矩阵下标。判定反复求和，先把矩形求和做快。

二维前缀和的四角公式，判定函数怎么写

二维前缀和先算好一张表 s：s[i][j] 存「左上角到某格」这块矩形的和。s 比原矩阵大一圈，第 0 行、第 0 列填 0（哨兵，省边界特判），s[i][j] 对应原矩阵 (i-1,j-1)。建表：s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1]。查左上角 (i,j)、边长 k 的和用四角（O(1)）：s[i+k][j+k] - s[i][j+k] - s[i+k][j] + s[i][j]。判定 check(k) 扫每个放得下的左上角，有一个和 ≤ threshold 就可行，否则不可行。

题面 3×7 矩阵、阈值 4，逐轮试边长

矩阵 3 行 7 列、每行 1 1 3 2 4 3 2、阈值 4。前缀表建完，起点 l=0、r=min(3,7)=3。第一轮 mid=(0+3+1)>>1=2，check(2) 首格 (0,0)：s[2][2]（左上块和）-s[0][2]-s[2][0]+s[0][0]=4-0-0+0=4≤4，命中，边长 2 可行，l=2。第二轮 mid=(2+3+1)>>1=3，check(3) 首格 (0,0)：s[3][3]-0-0+0=15>4，到末位 (0,4) 仍 >4，全失败，r=2；l=r=2，返回 2。

静默出错常藏两处：前缀表下标差一位、中点漏加 1

一个坑在下标：s 大一圈，s[i][j] 对应原矩阵 (i-1,j-1)，四角的 s[i+k][j+k] 全靠哨兵不越界，盯错一位整片算歪。另一个在中点：可行时 l=mid，中点须 (l+r+1)>>1 向上取整；写成 (l+r)>>1，区间剩两格时 mid 取到 l 又赋回 l，缩不动就死循环。题目要边长、别返回 k×k 面积。

复杂度：建表 O(m·n)，二分 log(min(m,n)) 轮、每轮扫 O(m·n) 个左上角各 O(1) 求和，合起来 O(m·n·log(min(m,n)))，空间 O(m·n)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        def check(k: int) -> bool:
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    v = s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j]
                    if v <= threshold:
                        return True
            return False

        m, n = len(mat), len(mat[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(mat, 1):
            for j, x in enumerate(row, 1):
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
        l, r = 0, min(m, n)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size(), n = mat[0].size();
        int s[m + 1][n + 1];
        memset(s, 0, sizeof(s));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        auto check = [&](int k) {
            for (int i = 0; i < m - k + 1; ++i) {
                for (int j = 0; j < n - k + 1; ++j) {
                    if (s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <= threshold) {
                        return true;
                    }
                }
            }
            return false;
        };
        int l = 0, r = min(m, n);
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

Java

import java.util.*;
class Solution {
    private int m;
    private int n;
    private int threshold;
    private int[][] s;

    public int maxSideLength(int[][] mat, int threshold) {
        m = mat.length;
        n = mat[0].length;
        this.threshold = threshold;
        s = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        int l = 0, r = Math.min(m, n);
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private boolean check(int k) {
        for (int i = 0; i < m - k + 1; ++i) {
            for (int j = 0; j < n - k + 1; ++j) {
                if (s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <= threshold) {
                    return true;
                }
            }
        }
        return false;
    }
}