二分查找 – 第 2 页

目标

给你两个整数数组 nums1 和 nums2 ，它们已经按非降序排序，请你返回两个数组的最小公共整数。如果两个数组 nums1 和 nums2 没有公共整数，请你返回 -1 。

如果一个整数在两个数组中都至少出现一次，那么这个整数是数组 nums1 和 nums2 公共的。

示例 1：

输入：nums1 = [1,2,3], nums2 = [2,4]
输出：2
解释：两个数组的最小公共元素是 2 ，所以我们返回 2 。

示例 2：

输入：nums1 = [1,2,3,6], nums2 = [2,3,4,5]
输出：2
解释：两个数组中的公共元素是 2 和 3 ，2 是较小值，所以返回 2 。

说明：

1 <= nums1.length, nums2.length <= 10^5
1 <= nums1[i], nums2[j] <= 10^9
nums1 和 nums2 都是非降序的。

思路

有两个升序数组 nums1 和 nums2，返回它们最小的公共元素。

双指针，如果不相等优先移动元素值较小的下标。

代码


/**
 * @date 2026-05-19 8:46
 */
public class GetCommon2540 {

    public int getCommon(int[] nums1, int[] nums2) {
        for (int a = 0, b = 0; a < nums1.length && b < nums2.length; ) {
            if (nums1[a] == nums2[b]) {
                return nums1[a];
            } else if (nums1[a] < nums2[b]) {
                a++;
            } else {
                b++;
            }
        }
        return -1;
    }
}

性能

目标

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须尽可能减少整个过程的操作步骤。

示例 1：

输入：nums = [1,3,5]
输出：1

示例 2：

输入：nums = [2,2,2,0,1]
输出：0

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶：这道题与 153.寻找旋转排序数组中的最小值类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

思路

数组 nums 由一个升序数组经过旋转而成，求数组的最小值，要求时间复杂度为 O(log n)。

与 153.寻找旋转排序数组中的最小值不同的是可能存在重复元素。预处理 r，使它指向不等于 nums[0] 的最大下标即可。

代码


/**
 * @date 2026-05-18 11:13
 */
public class FindMin154 {

    public int findMin(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (r >= 0 && nums[0] == nums[r]) {
            r--;
        }
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= nums[0]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return nums[l % n];
    }

}

性能

目标

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

说明：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

思路

数组 nums的 元素值互不相同，它由一个升序数组经过旋转而成，求数组的最小值，要求时间复杂度为 O(log n)。

所谓旋转，可以视为循环数组向右移动。虽然不是整体有序，但还是可以使用二分。由于元素值互不相同，根据第一个元素可以判断属于哪一部分，进而可以确定搜索方向。

如果大于第一个元素向右搜索，如果小于则向左搜索，注意如果返回的下标是 n 需要对 n 取余指向第一个元素。

代码


/**
 * @date 2024-08-31 22:37
 */
public class FindMin153 {

    public int findMin_v2(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= nums[0]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return nums[l % n];
    }

}

性能

目标

给你一个长度为偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是互补的。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组互补的最少操作次数。

示例 1：

输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。

示例 2：

输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。

示例 3：

输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。

说明：

n == nums.length
2 <= n <= 10^5
1 <= nums[i] <= limit <= 10^5
n 是偶数。

思路

有一个长度为偶数的数组 nums 和一个整数 limit，每次操作可以将任意元素替换为 [1, limit] 中的任意整数，求使得 nums 互补的最少操作次数。所谓互补指 nums[i] + nums[n - 1 - i] 的和都相等。

由于 1 <= nums[i] <= limit，每一对元素和都可以变成 [2, 2 * limit] 中的任意数字。

令 a = nums[i], b = nums[n - 1 - i], sum = a + b，如果只操作一次，考虑左侧 a -> 1 或者 b -> 1，sum 最多变化 max(a, b) - 1；右侧 a -> limit 或者 b -> limit，sum 最多变化 limit - min(a, b)。

将 sum 变成区间 [sum - (max(a, b) - 1), sum - 1], [sum + 1, sum + limit - min(a, b)] 内的值需要操作一次
变成 sum 的操作次数不变
其它 [2, sum - (max(a, b) - 1) - 1], [sum + limit - min(a, b) + 1, 2 * limit] 需要操作两次

使用差分数组来记录每对元素和变成目标和所需的操作次数，最后遍历所有目标和，取操作次数最小的即可。

代码


/**
 * @date 2026-05-13 10:13
 */
public class MinMoves1674 {

    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int max = 2 * limit;
        int[] diff = new int[max + 2];
        for (int i = 0; i < n / 2; i++) {
            int a = nums[i];
            int b = nums[n - 1 - i];
            int sum = a + b;
            int l = sum - (Math.max(a, b) - 1);
            int r = sum + (limit - Math.min(a, b));
            diff[2] += 2;
            diff[Math.max(2, l)]--;
            diff[sum]--;
            diff[Math.min(sum + 1, max + 1)]++;
            diff[Math.min(r + 1, max + 1)]++;
        }
        int sum = 0, res = Integer.MAX_VALUE;
        for (int i = 2; i <= max; i++) {
            sum += diff[i];
            res = Math.min(sum, res);
        }
        return res;
    }

}

性能

目标

给你一个整数 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

2026 年 11 月
一	二	三	四	五	六	日
						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