标签： hard

目标

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟。你想使用这些电池让 全部 n 台电脑 同时 运行。

一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

注意，你不能给电池充电。

请你返回你可以让 n 台电脑同时运行的 最长 分钟数。

示例 1：

输入：n = 2, batteries = [3,3,3]
输出：4
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。
2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。
在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。
在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。
我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。

示例 2：

输入：n = 2, batteries = [1,1,1,1]
输出：2
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。
一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。
1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。
我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。

说明：

• 1 <= n <= batteries.length <= 10^5
• 1 <= batteries[i] <= 10^9

思路

有 m 个电池，batteries[i] 表示第 i 个电池的电量，将电池分成 n 组，要求每组电池电量和的最小值最大。

贪心的做法是找到上界 x = sum / n，从大到小遍历电池容量：

• 如果大于 x，超过的部分也不能再使用了，因为一个电池在同一时间只能为一台电池供电，问题规模缩小，sum -= batteries[i]，n--。
• 如果小于等于 x，可以用完了再接上下一个电池，不会出现一个电池供两台电脑的情况，因为如果出现这种情况，总是可以将其放到一台的末尾与一台的开头将它们错开。

代码

/**
 * @date 2025-12-01 8:57
 */
public class MaxRunTime2141 {

    public long maxRunTime(int n, int[] batteries) {
        long sum = 0L;
        for (int battery : batteries) {
            sum += battery;
        }
        Arrays.sort(batteries);
        int m = batteries.length;
        for (int i = m - 1; i >= 0; i--) {
            long x = sum / n;
            if (batteries[i] <= x) {
                return x;
            }
            sum -= batteries[i];
            n--;
        }
        return -1;
    }
}

性能

目标

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 10^9 + 7 取余 的结果。

示例 1：

输入：grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出：2
解释：有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径，和为 5 + 2 + 4 + 5 + 2 = 18 ，能被 3 整除。
第二条路径为上图中用蓝色标注的路径，和为 5 + 3 + 0 + 5 + 2 = 15 ，能被 3 整除。

示例 2：

输入：grid = [[0,0]], k = 5
输出：1
解释：红色标注的路径和为 0 + 0 = 0 ，能被 5 整除。

示例 3：

输入：grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出：10
解释：每个数字都能被 1 整除，所以每一条路径的和都能被 k 整除。

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 5 * 10^4
• 1 <= m n <= 5 10^4
• 0 <= grid[i][j] <= 100
• 1 <= k <= 50

思路

有一个矩阵 grid，从左上角出发，只能向下或向右走，求到达右下角的路径中，路径和能被 k 整除的路径数目。

定义 dp[i][j][r] 表示从 (0, 0) 到达 (i, j) 的路径和 模 k 余 r 的路径总数，状态转移方程为 dp[i][j][r] = (dp[i - 1][j][(r + k - rem) % k] + dp[i][j - 1][(r + k - rem) % k]) % mod，其中 rem = grid[i][j] % k。

代码

/**
 * @date 2025-11-26 8:49
 */
public class NumberOfPaths2435 {

    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int mod = 1000000007;
        int[][][] dp = new int[m][n][k];
        int sum = 0;
        for (int i = 0; i < m; i++) {
            sum += grid[i][0];
            dp[i][0][sum % k] = 1;
        }
        sum = 0;
        for (int j = 0; j < n; j++) {
            sum += grid[0][j];
            dp[0][j][sum % k] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int rem = grid[i][j] % k;
                for (int r = 0; r < k; r++) {
                    dp[i][j][r] = (dp[i - 1][j][(r + k - rem) % k] + dp[i][j - 1][(r + k - rem) % k]) % mod;
                }
            }
        }
        return dp[m - 1][n - 1][0];
    }
}

性能

目标

给你一个二维整数数组 intervals ，其中 intervals[i] = [starti, endi] 表示从 starti 到 endi 的所有整数，包括 starti 和 endi 。

包含集合 是一个名为 nums 的数组，并满足 intervals 中的每个区间都 至少 有 两个 整数在 nums 中。

• 例如，如果 intervals = [[1,3], [3,7], [8,9]] ，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。

返回包含集合可能的最小大小。

示例 1：

输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：nums = [2, 3, 4, 8, 9].
可以证明不存在元素数量为 4 的包含集合。

示例 2：

输入：intervals = [[1,3],[1,4],[2,5],[3,5]]
输出：3
解释：nums = [2, 3, 4].
可以证明不存在元素数量为 2 的包含集合。 

示例 3：

输入：intervals = [[1,2],[2,3],[2,4],[4,5]]
输出：5
解释：nums = [1, 2, 3, 4, 5].
可以证明不存在元素数量为 4 的包含集合。 

说明：

• 1 <= intervals.length <= 3000
• intervals[i].length == 2
• 0 <= starti < endi <= 10^8

思路

定义包含集合是 与 intervals 中每个区间的交集大小至少为 2 的集合，求包含集合的最小 size。

根据 intervals 中每个区间的起点排序，倒序遍历区间，对于最后一个区间，显然优先选最左边的 2 个元素最优，将其按照从大到小顺序加入包含列表，接着访问下一个区间，判断包含集合的最小的两个元素是否在当前区间内：

• 如果都在，直接跳过
• 如果都不在，将当前区间左侧前两个元素按从大到小顺序加入包含列表
• 如果只有一个在，需要比较当前区间左端点 l 与包含集合最小元素 min 的关系，如果 min > l 将 l 加入列表，否则（即 min == l，由于是按起点排序的，所以 min 不会小于 l），用 l + 1 替换原来的列表最后一个元素，然后将 l 加入列表

代码

/**
 * @date 2025-11-20 8:46
 */
public class IntersectionSizeTwo757 {

    public int intersectionSizeTwo(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<Integer> res = new ArrayList<>();
        int p = 0;
        for (int i = n - 1; i >= 0; i--) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            if (p == 0 || res.get(p - 1) > r) {
                res.add(l + 1);
                res.add(l);
                p += 2;
            } else if (p > 1 && res.get(p - 2) > r) {
                if (res.get(p - 1) == l) {
                    res.set(p - 1, l + 1);
                }
                res.add(l);
                p++;
            }
        }
        return res.size();
    }

}

性能

目标

给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。

每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。

• |x| 表示 x 的 绝对值 。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。

一座城市的 电量 是所有能给它供电的供电站数目。

政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。

给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小电量的最大值是多少。

这 k 座供电站可以建在多个城市。

示例 1：

输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5 。
无法得到更优解，所以我们返回 5 。

示例 2：

输入：stations = [4,4,4,4], r = 0, k = 3
输出：4
解释：
无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。

说明：

• n == stations.length
• 1 <= n <= 10^5
• 0 <= stations[i] <= 10^5
• 0 <= r <= n - 1
• 0 <= k <= 10^9

思路

有 n 个城市，stations[i] 表示第 i 个城市的供电站数目，供电站可以为 r 范围内的城市供电，城市的电量定义为能够为它供电的电站数量。现在计划在这 n 个城市中额外建立 k 座供电站，求所有城市中最小电量的最大值是多少。

最大化最小值考虑枚举答案。贪心策略，如果当前城市供电量小于下限，则需要在 i + r 处建厂，因为前面的都已经满足了，在这里建厂可以更多地提高后面的下限。

代码

/**
 * @date 2025-11-07 10:57
 */
public class MaxPower2528 {

    public long maxPower(int[] stations, int r, int k) {
        int n = stations.length;
        long[] diff = new long[n + 1];
        long max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, stations[i]);
            int left = Math.max(0, i - r);
            int right = Math.min(n, i + r + 1);
            diff[left] += stations[i];
            diff[right] -= stations[i];
        }
        long left = 0, right = (max + k) * (r + 1);
        long m = left + (right - left) / 2;
        while (left <= right) {
            if (check(diff, m, k, r)) {
                left = m + 1;
            } else {
                right = m - 1;
            }
            m = left + (right - left) / 2;
        }

        return right;
    }

    public boolean check(long[] diff, long target, int k, int r) {
        long sum = 0;
        int n = diff.length;
        long[] tmp = new long[n];
        System.arraycopy(diff, 0, tmp, 0, n);
        for (int i = 0; i < n - 1; i++) {
            sum += tmp[i];
            if (sum >= target) {
                continue;
            }
            long c = target - sum;
            if (k >= c ) {
                tmp[Math.min(n - 1, i + r + r + 1)] -= c;
                sum = target;
                k -= c;
            } else {
                return false;
            }

        }
        return true;
    }

}

性能

目标

给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。

请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：

• 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

示例 1：

输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。

示例 2：

输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。

示例 3：

输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。

示例 4：

输入：target = [1,1,1,1]
输出：1

说明：

• 1 <= target.length <= 10^5
• 1 <= target[i] <= 10^5

思路

有一个 target 数组和一个与其维度相同的的全 0 数组 initial，每次操作可以将 initial 任意子数组的每个元素加 1。求将 initial 变为 target 的最小操作次数。

将子数组全部加一很容易想到差分数组，按照贪心的思想，要将元素从 0 操作为 target[i] 一定需要 target[i] 次，问题在于有多少个元素可以共用这一个操作。

计算差分数组，仅统计其中大于 0 的部分，小于等于 0 说明可以公用前面的操作，大于 0 说明需要增加操作。

代码

/**
 * @date 2025-10-30 8:57
 */
public class MinNumberOperations1526 {

    public int minNumberOperations(int[] target) {
        int n = target.length;
        int res = target[0];
        for (int i = 1; i < n; i++) {
            int diff = target[i] - target[i - 1];
            if (diff > 0) {
                res += diff;
            }
        }
        return res;
    }
}

性能

目标

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

你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以：

• 选择一个下标 i ，它在之前的操作中 没有 被选择过。
• 将 nums[i] 增加范围 [-k, k] 中的一个整数。

在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

示例 1：

输入：nums = [1,4,5], k = 1, numOperations = 2
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。

示例 2：

输入：nums = [5,11,20,20], k = 5, numOperations = 1
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 。

说明：

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

思路

对数组 nums 执行 numOperations 次操作，每次操作可以选一个没有被操作过的元素，将其增加 [-k, k] 之间的整数，求元素值的最大出现次数。

与 3346.执行操作后元素的最高频率I 相比，本题的数据范围更大，无法枚举值域。

考虑使用差分数组，由于数据范围太大，使用有序集合来维护。差分数组的前缀就是可以操作成该元素的频率，它不能超过原来已有的个数 + 操作次数。

代码

/**
 * @date 2025-10-21 10:34
 */
public class MaxFrequency3347 {

    public int maxFrequency(int[] nums, int k, int numOperations) {
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> diff = new TreeMap<>();
        for (int num : nums) {
            cnt.merge(num, 1, Integer::sum);
            diff.putIfAbsent(num, 0);
            diff.merge(num - k, 1, Integer::sum);
            diff.merge(num + k + 1, -1, Integer::sum);
        }
        int res = 0;
        int frequency = 0;
        for (Map.Entry<Integer, Integer> entry : diff.entrySet()) {
            frequency += entry.getValue();
            res = Math.max(res, Math.min(frequency, cnt.getOrDefault(entry.getKey(), 0) + numOperations));
        }
        return res;
    }
}

性能