标签： 贪心算法

目标

给定一个长度为 n 的整数数组 nums 和一个整数 k。

你必须从 nums 中选择 恰好 k 个非空子数组 nums[l..r]。子数组可以重叠，同一个子数组（相同的 l 和 r）可以 被选择超过一次。

子数组 nums[l..r] 的 值 定义为：max(nums[l..r]) - min(nums[l..r])。

总值 是所有被选子数组的 值 之和。

返回你能实现的 最大 可能总值。

子数组 是数组中连续的 非空 元素序列。

示例 1:

输入: nums = [1,3,2], k = 2
输出: 4
解释:
一种最优的方法是：
选择 nums[0..1] = [1, 3]。最大值为 3，最小值为 1，得到的值为 3 - 1 = 2。
选择 nums[0..2] = [1, 3, 2]。最大值仍为 3，最小值仍为 1，所以值也是 3 - 1 = 2。
将它们相加得到 2 + 2 = 4。

示例 2:

输入: nums = [4,2,5,1], k = 3
输出: 12
解释:
一种最优的方法是：
选择 nums[0..3] = [4, 2, 5, 1]。最大值为 5，最小值为 1，得到的值为 5 - 1 = 4。
选择 nums[1..3] = [2, 5, 1]。最大值为 5，最小值为 1，所以值也是 4。
选择 nums[2..3] = [5, 1]。最大值为 5，最小值为 1，所以值同样是 4。
将它们相加得到 4 + 4 + 4 = 12。

说明:

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

思路

定义子数组的值是最大值与最小值之差。已知一个长度为 n 的非负整数数组 nums，从中选择 k 个子数组（允许重复选择），求所选子数组的最大总值（即子数组值之和）。

由于可以重复选择，都选区间 [0, n - 1]，区间范围越大，最大值越大，最小值越小，差值越大。

代码

/**
 * @date 2026-06-09 9:07
 */
public class MaxTotalValue3689 {

    public long maxTotalValue(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        return (long) (max - min) * k;
    }
}

性能

目标

给你两种类别的游乐园项目：陆地游乐设施 和 水上游乐设施。

• 陆地游乐设施
  • landStartTime[i] – 第 i 个陆地游乐设施最早可以开始的时间。
  • landDuration[i] – 第 i 个陆地游乐设施持续的时间。
• 水上游乐设施
  • waterStartTime[j] – 第 j 个水上游乐设施最早可以开始的时间。
  • waterDuration[j] – 第 j 个水上游乐设施持续的时间。

一位游客必须从 每个 类别中体验 恰好一个 游乐设施，顺序 不限 。

• 游乐设施可以在其开放时间开始，或 之后任意时间 开始。
• 如果一个游乐设施在时间 t 开始，它将在时间 t + duration 结束。
• 完成一个游乐设施后，游客可以立即乘坐另一个（如果它已经开放），或者等待它开放。

返回游客完成这两个游乐设施的 最早可能时间 。

示例 1:

输入：landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
输出：9
解释：
方案 A（陆地游乐设施 0 → 水上游乐设施 0）：
在时间 landStartTime[0] = 2 开始陆地游乐设施 0。在 2 + landDuration[0] = 6 结束。
水上游乐设施 0 在时间 waterStartTime[0] = 6 开放。立即在时间 6 开始，在 6 + waterDuration[0] = 9 结束。
方案 B（水上游乐设施 0 → 陆地游乐设施 1）：
在时间 waterStartTime[0] = 6 开始水上游乐设施 0。在 6 + waterDuration[0] = 9 结束。
陆地游乐设施 1 在 landStartTime[1] = 8 开放。在时间 9 开始，在 9 + landDuration[1] = 10 结束。
方案 C（陆地游乐设施 1 → 水上游乐设施 0）：
在时间 landStartTime[1] = 8 开始陆地游乐设施 1。在 8 + landDuration[1] = 9 结束。
水上游乐设施 0 在 waterStartTime[0] = 6 开放。在时间 9 开始，在 9 + waterDuration[0] = 12 结束。
方案 D（水上游乐设施 0 → 陆地游乐设施 0）：
在时间 waterStartTime[0] = 6 开始水上游乐设施 0。在 6 + waterDuration[0] = 9 结束。
陆地游乐设施 0 在 landStartTime[0] = 2 开放。在时间 9 开始，在 9 + landDuration[0] = 13 结束。
方案 A 提供了最早的结束时间 9。

示例 2:

输入：landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
输出：14
解释：
方案 A（水上游乐设施 0 → 陆地游乐设施 0）：
在时间 waterStartTime[0] = 1 开始水上游乐设施 0。在 1 + waterDuration[0] = 11 结束。
陆地游乐设施 0 在 landStartTime[0] = 5 开放。立即在时间 11 开始，在 11 + landDuration[0] = 14 结束。
方案 B（陆地游乐设施 0 → 水上游乐设施 0）：
在时间 landStartTime[0] = 5 开始陆地游乐设施 0。在 5 + landDuration[0] = 8 结束。
水上游乐设施 0 在 waterStartTime[0] = 1 开放。立即在时间 8 开始，在 8 + waterDuration[0] = 18 结束。
方案 A 提供了最早的结束时间 14。

说明:

• 1 <= n, m <= 5 * 10^4
• landStartTime.length == landDuration.length == n
• waterStartTime.length == waterDuration.length == m
• 1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 10^5

思路

有两种游乐场项目，landStartTime[i]、landDuration[i] 分别表示陆上项目 i 的开始时间与持续时间，waterStartTime[i]、waterDuration[i] 分别表示水上项目 i 的开始时间与持续时间。游客需要分别游玩一个陆上项目和一个水上项目，返回最早的结束时间。

比 3633.最早完成陆地和水上游乐设施的时间I 数据范围更大，暴力解不可行。

要使完成时间最早，陆地与水上项目一定有一个是最早完成的 earliest，在此基础上另一个项目的最早完成时间为 Math.max(start, earliest) + duration。

代码

/**
 * @date 2026-06-04 10:28
 */
public class EarliestFinishTime3635 {

    public int earliestFinishTime(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
        int n = landStartTime.length;
        int m = waterStartTime.length;
        int landEarliest = Integer.MAX_VALUE;
        int waterEarliest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            landEarliest = Math.min(landEarliest, landStartTime[i] + landDuration[i]);
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            res = Math.min(res, Math.max(landEarliest, waterStartTime[i]) + waterDuration[i]);
            waterEarliest = Math.min(waterEarliest, waterStartTime[i] + waterDuration[i]);
        }
        for (int i = 0; i < n; i++) {
            res = Math.min(res, Math.max(waterEarliest, landStartTime[i]) + landDuration[i]);
        }
        return res;
    }
}

性能

目标

给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。

你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被 摧毁 ，并且行星会 获得 这颗小行星的质量。否则，行星将被摧毁。

如果所有小行星 都 能被摧毁，请返回 true ，否则返回 false 。

示例 1：

输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
所有小行星都被摧毁。

示例 2：

输入：mass = 5, asteroids = [4,9,23,4]
输出：false
解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。

说明：

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

思路

有一颗行星质量为 mass，还有一些小行星 asteroids，asteroids[i] 表示第 i 颗小行星的质量。可以让小行星以任意顺序碰撞行星，如果行星质量大于等于小行星，那么小行星被摧毁，行星获得其质量，否则行星被摧毁。判断是否所有小行星都可以被摧毁。

使用有序集合，每次获得比行星质量小的所有小行星质量。

代码

/**
 * @date 2026-06-01 10:14
 */
public class AsteroidsDestroyed2126 {

    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        TreeMap<Long, Integer> ts = new TreeMap<>();
        for (int a : asteroids) {
            ts.merge((long) a, 1, Integer::sum);
        }
        long m = mass;
        Long next = ts.floorKey(m);
        while (!ts.isEmpty() && next != null) {
            m += next * ts.get(next);
            ts.remove(next);
            next = ts.floorKey(m);
        }
        return ts.isEmpty();
    }

}

性能

目标

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。

单值网格 是全部元素都相等的网格。

返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。

示例 1：

输入：grid = [[2,4],[6,8]], x = 2
输出：4
解释：可以执行下述操作使所有元素都等于 4 ： 
- 2 加 x 一次。
- 6 减 x 一次。
- 8 减 x 两次。
共计 4 次操作。

示例 2：

输入：grid = [[1,5],[2,3]], x = 1
输出：5
解释：可以使所有元素都等于 3 。

示例 3：

输入：grid = [[1,2],[3,4]], x = 2
输出：-1
解释：无法使所有元素相等。

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• 1 <= x, grid[i][j] <= 10^4

思路

有一个 m x n 矩阵，每次操作可以将矩阵中的任意元素 +x 或者 -x，求使得矩阵所有元素相等所需的最小操作，如果不能返回 -1。

所有元素对 x 取模余数相同才有解，因为操作无法改变这个余数，而目标是将元素变成同一个数。

如果有解，可以将共同的余数减去，将每个元素都除以 x，然后令 x = 1，问题变成找到一个值，使得所有元素到这个值的距离之和最小。

这是一个 L1 优化问题，它的解是中位数，可以先排序，再取中间的元素即可。

代码

/**
 * @date 2026-04-28 9:35
 */
public class MinOperations2033 {

    public int minOperations(int[][] grid, int x) {
        int m = grid.length;
        int n = grid[0].length;
        int[] arr = new int[m * n];
        int rem = grid[0][0] % x;
        int k = 0;
        for (int[] row : grid) {
            for (int e : row) {
                if (e % x != rem) {
                    return -1;
                }
                arr[k++] = e / x;
            }
        }
        Arrays.sort(arr);
        int median = arr[arr.length / 2];
        int res = 0;
        for (int num : arr) {
            res += Math.abs(num - median);
        }
        return res;
    }
}

性能