二分查找 – shelterofly

目标

给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。

同时给你一个正整数 k 和一个二维整数数组 points，其中 points[i] = [xi, yi] 表示一个点在正方形边界上的坐标。

你需要从 points 中选择 k 个元素，使得任意两个点之间的最小曼哈顿距离最大化。

返回选定的 k 个点之间的最小曼哈顿距离的最大可能值。

两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。

示例 1：

输入： side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4
输出： 2
解释：
选择所有四个点。

示例 2：

输入： side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4
输出： 1
解释：
选择点 (0, 0) ，(2, 0) ，(2, 2) 和 (2, 1)。

示例 3：

输入： side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5
输出： 1
解释：
选择点 (0, 0) ，(0, 1) ，(0, 2) ，(1, 2) 和 (2, 2)。

说明：

1 <= side <= 10^9
4 <= points.length <= min(4 side, 15 10^3)
points[i] == [xi, yi]
输入产生方式如下：
- points[i] 位于正方形的边界上。
- 所有 points[i] 都互不相同。
4 <= k <= min(25, points.length)

思路

代码

性能

目标

给你两个非递增的整数数组 nums1 和 nums2 ，数组下标均从 0 开始计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为有效下标对，该下标对的距离为 j - i 。

返回所有有效下标对 (i, j) 中的最大距离。如果不存在有效下标对，返回 0 。

一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个非递增数组。

示例 1：

输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

示例 2：

输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。

示例 3：

输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

说明：

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[j] <= 10^5
nums1 和 nums2 都是非递增数组

思路

有两个非递增的整数数组 nums1 和 nums2，返回有效下标对的最大距离，如果不存在有效下标对，返回 0。有效下标对 (i, j) 需要满足 i <= j && nums1[i] <= nums2[j]。

二分查找 nums2 大于等于 nums1[i] 的最大下标，记录 j - i 的最大值。

代码


/**
 * @date 2026-04-19 23:44
 */
public class MaxDistance1855 {

    public int maxDistance(int[] nums1, int[] nums2) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            int j = upperBound(nums2, i, nums1[i]);
            res = Math.max(res, j - i);
        }
        return res;
    }

    public int upperBound(int[] arr, int l, int target) {
        int r = arr.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (arr[m] >= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }
}

性能

目标

给你一个环形数组 nums 和一个数组 queries 。

对于每个查询 i ，你需要找到以下内容：

数组 nums 中下标 queries[i] 处的元素与任意其他下标 j（满足 nums[j] == nums[queries[i]]）之间的最小距离。如果不存在这样的下标 j，则该查询的结果为 -1 。

返回一个数组 answer，其大小与 queries 相同，其中 answer[i] 表示查询i的结果。

示例 1：

输入： nums = [1,3,1,4,1,3,2], queries = [0,3,5]
输出： [2,-1,3]
解释：
查询 0：下标 queries[0] = 0 处的元素为 nums[0] = 1 。最近的相同值下标为 2，距离为 2。
查询 1：下标 queries[1] = 3 处的元素为 nums[3] = 4 。不存在其他包含值 4 的下标，因此结果为 -1。
查询 2：下标 queries[2] = 5 处的元素为 nums[5] = 3 。最近的相同值下标为 1，距离为 3（沿着循环路径：5 -> 6 -> 0 -> 1）。

示例 2：

输入： nums = [1,2,3,4], queries = [0,1,2,3]
输出： [-1,-1,-1,-1]
解释：
数组 nums 中的每个值都是唯一的，因此没有下标与查询的元素值相同。所有查询的结果均为 -1。

说明：

1 <= queries.length <= nums.length <= 10^5
1 <= nums[i] <= 10^6
0 <= queries[i] < nums.length

思路

有一个环形数组 nums 和一个查询数组 queries，返回元素值与 queries[i] 相同的其它元素之间的最小距离，如果不存在则结果为 -1，返回查询结果数组。

根据元素值分组，分组内记录下标。针对每个查询，二分查找元素在分组中的位置，比较前后下标的距离，如果分组只有一个元素，返回 -1。需要特殊处理首与尾的最近距离。

也可以分组后预处理每个位置的最近距离，统一计算前后的最近距离，查询时直接取结果即可。注意循环数组的距离处理，这里直接将超出的距离映射回了原数组下标，因此最近距离需要取 min(d, n - d)，其中 d = abs(i - j) 表示下标 i 与 j 的距离。

代码


/**
 * @date 2026-04-16 8:55
 */
public class SolveQueries3488 {

    public List<Integer> solveQueries_v1(int[] nums, int[] queries) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(nums[i], new ArrayList<>());
            map.get(nums[i]).add(i);
        }
        int[] dis = new int[n];
        for (List<Integer> list : map.values()) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                int index = list.get(i);
                if (size >= 2) {
                    int prev = Math.abs(index - list.get((size + i - 1) % size));
                    int next = Math.abs(list.get((i + 1) % size) - index);
                    dis[index] = Math.min(Math.min(prev, n - prev), Math.min(next, n - next));
                } else {
                    dis[index] = -1;
                }
            }
        }
        List<Integer> res = new ArrayList<>(queries.length);
        for (int query : queries) {
            res.add(dis[query]);
        }
        return res;
    }

}

性能

目标

一条无限长的直线上分布着一些机器人和墙壁。给你整数数组 robots ，distance 和 walls：

robots[i] 是第 i 个机器人的位置。
distance[i] 是第 i 个机器人的子弹可以行进的最大距离。
walls[j] 是第 j 堵墙的位置。

每个机器人有一颗子弹，可以向左或向右发射，最远距离为 distance[i] 米。

子弹会摧毁其射程内路径上的每一堵墙。机器人是固定的障碍物：如果子弹在到达墙壁前击中另一个机器人，它会立即在该机器人处停止，无法继续前进。

返回机器人可以摧毁墙壁的最大数量。

注意：

墙壁和机器人可能在同一位置；该位置的墙壁可以被该位置的机器人摧毁。
机器人不会被子弹摧毁。

示例 1:

输入: robots = [4], distance = [3], walls = [1,10]
输出: 1
解释:
robots[0] = 4 向 左 发射，distance[0] = 3，覆盖范围 [1, 4]，摧毁了 walls[0] = 1。
因此，答案是 1。

示例 2:

输入: robots = [10,2], distance = [5,1], walls = [5,2,7]
输出: 3
解释:
robots[0] = 10 向 左 发射，distance[0] = 5，覆盖范围 [5, 10]，摧毁了 walls[0] = 5 和 walls[2] = 7。
robots[1] = 2 向 左 发射，distance[1] = 1，覆盖范围 [1, 2]，摧毁了 walls[1] = 2。
因此，答案是 3。

示例 3:

输入: robots = [1,2], distance = [100,1], walls = [10]
输出: 0
解释:
在这个例子中，只有 robots[0] 能够到达墙壁，但它向 右 的射击被 robots[1] 挡住了，因此答案是 0。

说明:

1 <= robots.length == distance.length <= 10^5
1 <= walls.length <= 10^5
1 <= robots[i], walls[j] <= 10^9
1 <= distance[i] <= 10^5
robots 中的所有值都是互不相同的
walls 中的所有值都是互不相同的

思路

无限长的直线上分布着一些机器人（位于 robots[i]）和墙壁（位于 walls[j]），机器人可以向左或向右发射一枚子弹，位于 robots[i] 的机器人发射的子弹最多可以行进 distance[i]。子弹会摧毁其射程内路径上的每一堵墙，子弹不能摧毁或穿过机器人，求摧毁墙的最大数目。所有机器人的位置都是互不相同的，所有墙的位置也是互不相同的。

根据机器人的位置排序，考虑相邻机器人可以摧毁的墙的数目。定义 dp[i][k] 表示前 i 个机器人摧毁墙的最大数目，且第 i 个机器人朝 k 发射子弹，k = 0 表示向左， k = 1 表示向右。walls(from, to) 表示区间 [from, to] 内的墙的个数。

dp[i][0] = max(dp[i - 1][0] + walls(max(prev + 1, cur - dcur), cur), dp[i - 1][1] + walls(max(prev + dprev + 1, cur - dcur), cur))
dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + walls(cur, min(cur + dcur, next - 1))
当前机器人向左射，需要考虑前一个机器人的射击方向，如果前一个机器人也向左射，只需考虑区间 [max(prev + 1, cur - dcur), cur] 中墙的个数，如果向右射则需要考虑 [max(prev + dprev + 1, cur - dcur), cur] 中墙的个数。其中 dcur 表示位于 cur 的机器人的射击距离，dprev 表示位于 prev 机器人的射击距离。
当前机器人向右射，无需考虑前一个机器人的射击方向，取二者最大的即可，当前机器人向右射的范围是 [cur, min(cur + dcur, next - 1)]，注意特殊处理最后一个机器人，没有 next 时取 Integer.MAX_VALUE。

剩下的问题是如何快速获取区间内墙的数量，由于不涉及更新，可以直接二分获得上下界。

代码


/**
 * @date 2026-04-03 10:14
 */
public class MaxWalls3661 {

    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        Arrays.sort(walls);
        int n = robots.length;
        Integer[] index = new Integer[n];
        Arrays.setAll(index, i -> i);
        Arrays.sort(index, (a, b) -> robots[a] - robots[b]);
        int[][] dp = new int[n][2];
        Integer first = index[0];
        dp[0][0] = getWalls(walls, robots[first] - distance[first], robots[first]);
        dp[0][1] = getWalls(walls, robots[first], Math.min(robots[first] + distance[first], n > 1 ? robots[index[1]] - 1 : Integer.MAX_VALUE));
        for (int i = 1; i < n; i++) {
            Integer cur = index[i];
            Integer prev = index[i - 1];
            dp[i][0] = Math.max(dp[i - 1][0] + getWalls(walls, Math.max(robots[prev] + 1, robots[cur] - distance[cur]), robots[cur]),
                    dp[i - 1][1] + getWalls(walls, Math.max(robots[cur] - distance[cur], robots[prev] + distance[prev] + 1), robots[cur]));
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]) + getWalls(walls, robots[cur], Math.min(robots[cur] + distance[cur], i < n - 1 ? robots[index[i + 1]] - 1 : Integer.MAX_VALUE));
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }

    /**
     * 获取 [from, to] 之间的墙的数量
     */
    public int getWalls(int[] walls, int from, int to) {
        int r = upperBound(walls, to);
        int l = lowerBound(walls, from);
        if (r < l) {
            return 0;
        }
        return r - l + 1;
    }

    /**
     * 返回 <= target 的最大下标
     */
    public int upperBound(int[] walls, int target) {
        int l = 0, r = walls.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (walls[m] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

    /**
     * 返回 >= target 的最小下标
     */
    public int lowerBound(int[] walls, int target) {
        int l = 0, r = walls.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (walls[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

}

性能

目标

给你一个整数 mountainHeight 表示山的高度。

同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。

工人们需要同时进行工作以降低山的高度。对于工人 i :

山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] 2 + ... + workerTimes[i] x 秒。例如：
- 山的高度降低 1，需要 workerTimes[i] 秒。
- 山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。

返回一个整数，表示工人们使山的高度降低到 0 所需的最少秒数。

示例 1：

输入： mountainHeight = 4, workerTimes = [2,1,1]
输出： 3
解释：
将山的高度降低到 0 的一种方式是：
工人 0 将高度降低 1，花费 workerTimes[0] = 2 秒。
工人 1 将高度降低 2，花费 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
工人 2 将高度降低 1，花费 workerTimes[2] = 1 秒。
因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒。

示例 2：

输入： mountainHeight = 10, workerTimes = [3,2,2,4]
输出： 12
解释：
工人 0 将高度降低 2，花费 workerTimes[0] + workerTimes[0] * 2 = 9 秒。
工人 1 将高度降低 3，花费 workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 秒。
工人 2 将高度降低 3，花费 workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 秒。
工人 3 将高度降低 2，花费 workerTimes[3] + workerTimes[3] * 2 = 12 秒。
所需的最少时间为 max(9, 12, 12, 12) = 12 秒。

示例 3：

输入： mountainHeight = 5, workerTimes = [1]
输出： 15
解释：
这个示例中只有一个工人，所以答案是 workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15 秒。

说明：

1 <= mountainHeight <= 10^5
1 <= workerTimes.length <= 10^4
1 <= workerTimes[i] <= 10^6

思路

整数 mountainHeight 表示山的高度，workerTimes[i] 表示工人 i 的时效，工人 i 将山的高度降低 x 所需的时间是 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x，求工人同时工作，将山的高度降为 0 所需要的最少时间。

移山所需的时间是所有工人消耗时间的最大值，最小化这个最大值，可以考虑二分答案。

工人 i 将高度降低 x 所需时间为 workerTimes[i] * (1 + 2 + …… + x) = workerTimes[i] * (1 + x) * x / 2。如果最大时间是 target，解方程可得工人 i 最多将高度降低 (sqrt(1 + (8 * target) / workerTimes[i]) - 1) / 2，只需判断降低的高度是否超过 mountainHeight 即可。

代码


/**
 * @date 2026-03-13 9:42
 */
public class MinNumberOfSeconds3296 {

    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int max = 0;
        int n = workerTimes.length;
        for (int wt : workerTimes) {
            max = Math.max(max, wt);
        }
        long p = (mountainHeight - 1) / n + 1;
        long l = 0L, r = max * (1 + p) * p / 2;
        long m = l + (r - l) / 2;
        while (l <= r) {
            if (check(mountainHeight, workerTimes, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    public boolean check(int mountainHeight, int[] workerTimes, long target) {
        int total = 0;
        for (int w : workerTimes) {
            total += (int) (Math.sqrt(1 + (8 * target) / w) - 1) / 2;
            if (total >= mountainHeight) {
                return true;
            }
        }
        return false;
    }

}

性能

3600.升级后最大生成树稳定性

目标

给你一个整数 n，表示编号从 0 到 n - 1 的 n 个节点，以及一个 edges 列表，其中 edges[i] = [ui, vi, si, musti]：

ui 和 vi 表示节点 ui 和 vi 之间的一条无向边。
si 是该边的强度。
musti 是一个整数（0 或 1）。如果 musti == 1，则该边必须包含在生成树中，且不能升级。

你还有一个整数 k，表示你可以执行的最多升级次数。每次升级会使边的强度翻倍，且每条可升级边（即 musti == 0）最多只能升级一次。

一个生成树的稳定性定义为其中所有边的最小强度。

返回任何有效生成树可能达到的最大稳定性。如果无法连接所有节点，返回 -1。

注意：图的一个生成树（spanning tree）是该图中边的一个子集，它满足以下条件：

将所有节点连接在一起（即图是连通的）。
不形成任何环。
包含恰好 n - 1 条边，其中 n 是图中节点的数量。

示例 1：

输入： n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1
输出： 2
解释：
边 [0,1] 强度为 2，必须包含在生成树中。
边 [1,2] 是可选的，可以使用一次升级将其强度从 3 提升到 6。
最终的生成树包含这两条边，强度分别为 2 和 6。
生成树中的最小强度是 2，即最大可能稳定性。

示例 2：

输入： n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2
输出： 6
解释：
所有边都是可选的，且最多可以进行 k = 2 次升级。
将边 [0,1] 从 4 升级到 8，将边 [1,2] 从 3 升级到 6。
生成树包含这两条边，强度分别为 8 和 6。
生成树中的最小强度是 6，即最大可能稳定性。

示例 3：

输入： n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0
输出： -1
解释：
所有边都是必选的，构成了一个环，这违反了生成树无环的性质。因此返回 -1。

说明：

2 <= n <= 10^5
1 <= edges.length <= 10^5
edges[i] = [ui, vi, si, musti]
0 <= ui, vi < n
ui != vi
1 <= si <= 10^5
musti 是 0 或 1。
0 <= k <= n
没有重复的边。

思路

// todo

代码

性能

3634.使数组平衡的最少移除数目

目标

给你一个整数数组 nums 和一个整数 k。

如果一个数组的最大元素的值至多是其最小元素的 k 倍，则该数组被称为是平衡的。

你可以从 nums 中移除任意数量的元素，但不能使其变为空数组。

返回为了使剩余数组平衡，需要移除的元素的最小数量。

注意：大小为 1 的数组被认为是平衡的，因为其最大值和最小值相等，且条件总是成立。

示例 1:

输入：nums = [2,1,5], k = 2
输出：1
解释：
移除 nums[2] = 5 得到 nums = [2, 1]。
现在 max = 2, min = 1，且 max <= min * k，因为 2 <= 1 * 2。因此，答案是 1。

示例 2:

输入：nums = [1,6,2,9], k = 3
输出：2
解释：
移除 nums[0] = 1 和 nums[3] = 9 得到 nums = [6, 2]。
现在 max = 6, min = 2，且 max <= min * k，因为 6 <= 2 * 3。因此，答案是 2。

示例 3:

输入：nums = [4,6], k = 2
输出：0
解释：
由于 nums 已经平衡，因为 6 <= 4 * 2，所以不需要移除任何元素。

说明：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^5

思路

定义平衡数组是 元素最大值 <= k * 元素最小值 的数组。有一个数组 nums，每次操作可以移除一个元素，求使得数组变成平衡数组的最少操作次数。

直接二分查找大于 k * nums[i] 的最小下标 index，删掉的元素是前面 i 个元素（下标 i 其实是第 i + 1 个元素，前面有 i 个），加上 n - 1 - index + 1 个大于 k * nums[i] 的元素。

可以使用滑动窗口，删掉的元素就是总长度减去窗口内的元素，针对每一个 left 将其扩展到最右端，然后移出 left 继续判断。

代码


/**
 * @date 2026-02-06 8:54
 */
public class MinRemoval3634 {

    public int minRemoval(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = n - 1;
        int r = 0;
        for (int l = 0; l < n; l++) {
            while (r < n && (long) nums[l] * k >= nums[r]) {
                r++;
            }
            res = Math.min(res, n - (r - l));
        }
        return res;
    }

}

性能

744.寻找比目标字母大的最小字母

目标

给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

示例 1：

输入: letters = ['c', 'f', 'j']，target = 'a'
输出: 'c'
解释：letters 中字典上比 'a' 大的最小字符是 'c'。

示例 2:

输入: letters = ['c','f','j'], target = 'c'
输出: 'f'
解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:

输入: letters = ['x','x','y','y'], target = 'z'
输出: 'x'
解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。

说明：

2 <= letters.length <= 10^4
letters[i] 是一个小写字母
letters 按非递减顺序排序
letters 最少包含两个不同的字母
target 是一个小写字母

思路

有一个升序排列的字符数组 letters，返回大于 target 的最小字符，如不存在返回第一个字符。

使用二分，查找第一个大于 target 的字符。

代码


/**
 * @date 2026-02-02 9:42
 */
public class NextGreatestLetter744 {

    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int r = n - 1;
        int l = 0;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (letters[m] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return l < n ? letters[l] : letters[0];
    }

}

性能

1292.元素和小于等于阈值的正方形的最大边长

目标

给你一个大小为 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 x n 矩阵，返回其中元素和不超过 threshold 的正方形的最大边长。

使用二维前缀和计算面积，枚举右下顶点与边长，边长从已知的最大值开始枚举，超出 threshold 就退出循环，时间复杂度为 O(mn + min(m, n))。

代码


/**
 * @date 2026-01-19 9:46
 */
public class MaxSideLength1292 {

    public int maxSideLength_v1(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = prefix[i][j - 1] + mat[i - 1][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];
                int l = Math.min(i, j);
                for (int k = res + 1; k <= l; k++) {
                    int area = prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k];
                    if (area <= threshold) {
                        res = Math.max(res, k);
                    } else {
                        break;
                    }
                }
            }
        }
        return res;
    }

}

性能

3453.分割正方形I

目标

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积等于该线以下正方形的总面积。

答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。

注意：正方形可能会重叠。重叠区域应该被多次计数。

示例 1：

输入： squares = [[0,0,1],[2,2,1]]
输出： 1.00000
解释：
任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

示例 2：

输入： squares = [[0,0,2],[1,1,1]]
输出： 1.16667
解释：
面积如下：
线下的面积：7/6 * 2 (红色) + 1/6 (蓝色) = 15/6 = 2.5。
线上的面积：5/6 * 2 (红色) + 5/6 (蓝色) = 15/6 = 2.5。
由于线以上和线以下的面积相等，输出为 7/6 = 1.16667。

说明：

1 <= squares.length <= 5 * 10^4
squares[i] = [xi, yi, li]
squares[i].length == 3
0 <= xi, yi <= 10^9
1 <= li <= 10^9
所有正方形的总面积不超过 10^12。

思路

二维平面内有一些正方形，squares[i] = [xi, yi, li] 表示正方形坐下顶点坐标为 (xi, yi)，边长为 li。找到最小的 y 水平线，使得这些正方形在水平线上方的面积等于下方的面积，重叠部分的面积应被重复计算。

二分答案，计算上方与下方的面积。

代码


/**
 * @date 2026-01-13 9:08
 */
public class SeparateSquares3453 {

    public double separateSquares(int[][] squares) {
        double l = 0.0, r = 1000000000.0;
        double m = l + (r - l) / 2;
        while (l <= r) {
            if (check(squares, m)) {
                r = m - 0.00001;
            } else {
                l = m + 0.00001;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    private boolean check(int[][] squares, double m) {
        double upperSum = 0.0, lowerSum = 0.0;
        for (int[] square : squares) {
            int y = square[1], l = square[2];
            if (y + l <= m) {
                lowerSum += (double) l * l;
            } else if (y >= m) {
                upperSum += (double) l * l;
            } else {
                upperSum += (double) l * (y + l - m);
                lowerSum += (double) l * (m - y);
            }
        }
        return upperSum <= lowerSum;
    }

}

2026 年 4 月
一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30