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

这道题到底在问什么

输入

mat = 全是 2 的 5×5,threshold = 1

输出

0(随便哪个单格都是 2,已经 > 1)

输入

mat = [[1,1,3,2,4,3,2] 重复三行],threshold = 4

输出

2

输入

本节演示 3×4 矩阵,threshold = 8

输出

2

最优解：一步一步想明白

1. 3记住两招:二维前缀和把矩形求和压到 O(1);边长可行性单调,于是二分边长。可行往大找,不可行往小缩。
2. 4这是一张 3 行 4 列的矩阵,行号 0 到 2、列号 0 到 3。我们要在它里面框一个正方形,使框住的数字之和不超过 8,并且边长尽量大。第一步不是急着去框,而是先把下面这张前缀和表建出来,它能让后面任何一次正方形求和都只花常数时间。
3. 5前缀和表 s 故意比原矩阵大一圈,行列各多出一个 0 号。多出来的第 0 行、第 0 列全部填 0,叫哨兵。有了这圈 0,内部每一格都能统一用「上邻加左邻减左上邻再加本格」这一条公式来算,不用为最上行、最左列单独写边界判断。下面从 i 等于 1、j 等于 1 开始,一行一行把内部填满。
4. 6算 s[1][1]:它代表从矩阵左上角一直到原矩阵第 0 行第 0 列(值是 4)这块矩形的总和。正上方那块是 0,正左方那块是 0,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 4,得到 4。
5. 7算 s[1][2]:它代表从矩阵左上角一直到原矩阵第 0 行第 1 列(值是 3)这块矩形的总和。正上方那块是 0,正左方那块是 4,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 3,得到 7。
6. 8算 s[1][3]:它代表从矩阵左上角一直到原矩阵第 0 行第 2 列(值是 1)这块矩形的总和。正上方那块是 0,正左方那块是 7,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 8。
7. 9算 s[1][4]:它代表从矩阵左上角一直到原矩阵第 0 行第 3 列(值是 1)这块矩形的总和。正上方那块是 0,正左方那块是 8,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 9。
8. 10算 s[2][1]:它代表从矩阵左上角一直到原矩阵第 1 行第 0 列(值是 2)这块矩形的总和。正上方那块是 4,正左方那块是 0,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 2,得到 6。
9. 11算 s[2][2]:它代表从矩阵左上角一直到原矩阵第 1 行第 1 列(值是 4)这块矩形的总和。正上方那块是 7,正左方那块是 6,这两块把左上角那一小块 4 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 4,得到 13。
10. 12算 s[2][3]:它代表从矩阵左上角一直到原矩阵第 1 行第 2 列(值是 1)这块矩形的总和。正上方那块是 8,正左方那块是 13,这两块把左上角那一小块 7 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 15。
11. 13算 s[2][4]:它代表从矩阵左上角一直到原矩阵第 1 行第 3 列(值是 1)这块矩形的总和。正上方那块是 9,正左方那块是 15,这两块把左上角那一小块 8 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 17。
12. 14算 s[3][1]:它代表从矩阵左上角一直到原矩阵第 2 行第 0 列(值是 3)这块矩形的总和。正上方那块是 6,正左方那块是 0,这两块把左上角那一小块 0 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 3,得到 9。
13. 15算 s[3][2]:它代表从矩阵左上角一直到原矩阵第 2 行第 1 列(值是 1)这块矩形的总和。正上方那块是 13,正左方那块是 9,这两块把左上角那一小块 6 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 17。
14. 16算 s[3][3]:它代表从矩阵左上角一直到原矩阵第 2 行第 2 列(值是 2)这块矩形的总和。正上方那块是 15,正左方那块是 17,这两块把左上角那一小块 13 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 2,得到 21。
15. 17算 s[3][4]:它代表从矩阵左上角一直到原矩阵第 2 行第 3 列(值是 1)这块矩形的总和。正上方那块是 17,正左方那块是 21,这两块把左上角那一小块 15 都算了一遍,重复了,要减掉一次,最后再补上本格自己的 1,得到 24。
16. 18十二个内部格全部填好。现在这张表里,s[i][j] 就是「从矩阵左上角到 (i-1,j-1) 」那块矩形的总和。接下来不再碰原始数字,所有正方形求和都靠这张表的四个角加加减减。边长该取多大?用二分:行列里小的那个是 3,所以边长在 0 到 3 之间,我们二分着试。
17. 19二分开始。左端 l 是 0,右端 r 是行列较小值 3。取中点 mid,这里用 (l 加 r 加 1) 右移一位,等于 2;加 1 是让中点往上取整,后面 l 会跳到 mid,不补这个 1 会死循环。现在就去检查:边长 2 的正方形,能不能找到一个和 ≤ 8 的。
18. 20检查边长 2,从最靠左上的位置 (0,0) 开始。它的正方形和用四个角算:右下角 s[2][2] 是 13,减掉右上角 s[0][2] 和左下角 s[2][0],再把被减了两次的左上角 s[0][0] 加回来,得到 13。这个值大于 8,这个位置框不下,换右边一个位置。
19. 21左上角右移到 (0,1)。同样用四个角:15 减 0 减 6 加 0,等于 9。还是大于 8,继续往右挪。注意四个角的下标都跟着左上角一起平移,这就是 O(1) 的好处,挪一格不用重新加里面的数。
20. 22再往右到 (0,2)。四个角:17 减 0 减 13 加 0,等于 4。这回 4 不超过 8,找到了一个合格的边长 2 正方形。只要有一个合格就够了,立刻收手:边长 2 可行。
21. 23边长 2 行得通,说明答案至少是 2,我们贪心地想要更大,把左端 l 抬到 2。新区间是 2 到 3,中点 (2 加 3 加 1) 右移一位等于 3。接着去试边长 3 能不能也找到一个和 ≤ 8 的正方形。
22. 24检查边长 3,3 行 4 列里能放下 3×3 的左上角只有两个。先看 (0,0):右下角 s[3][3] 是 21,减右上 0、减左下 0、加回左上 0,得 21。远大于 8,框不下。
23. 25挪到 (0,1):24 减 0 减 9 加 0,等于 15,还是大于 8。两个位置都失败,边长 3 找不到合格正方形,不可行。
24. 26边长 3 不可行,把右端 r 压到 2。现在 l 和 r 都等于 2,区间只剩一个值,二分结束。整个过程里能成立的最大边长就是 2,这就是答案。注意题目要的是边长本身,返回 2,不是面积 4。
25. 27把答案放回原矩阵看:就是右上角这个 2×2 区块,左上角在行 0 列 2,盖住行 0 到 1、列 2 到 3,四个数都是 1,加起来 4,不超过 8。它的边长是 2。边长 3 试过框不下,边长 2 框得下,所以最大边长就是 2。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

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

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

复杂度

面试官可能追问