标签： 贪心算法

目标

给你一个字符串 word，由小写英文字母组成。

电话键盘上的按键与 不同 小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。

现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母，但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。

返回重新映射按键后输入 word 所需的 最少 按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不 对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xyzxyzxyzxyz"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 3 上按一次
"z" -> 在按键 4 上按一次
总成本为 1 * 4 + 1 * 4 + 1 * 4 = 12 。
可以证明不存在其他成本更低的映射方案。
注意按键 9 没有映射到任何字母：不必让每个按键都存在与之映射的字母，但是每个字母都必须映射到按键上。

示例 3：

输入：word = "aabbccddeeffgghhiiiiii"
输出：24
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
"f" -> 在按键 7 上按一次
"g" -> 在按键 8 上按一次
"h" -> 在按键 9 上按两次
"i" -> 在按键 9 上按一次
总成本为 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24 。
可以证明不存在其他成本更低的映射方案。

说明：

• 1 <= word.length <= 10^5
• word 仅由小写英文字母组成。

思路

可以将 26 个字母映射到 2 ~ 9 按键上，比如将 abc 映射到 2，那么输入 b 需要按两下 2，输入 c 需要按三下 2。给定一个单词 word，返回输入该字符所需的最少按键次数。

与 3014.输入单词需要的最少按键次数I 相比，本题并没有说 word 是由不同字母组成。

将字母出现频次从大到小排序，大的优先分配在按键的第一个位置（按一下），然后是第二个位置（按两下），以此类推。

代码

/**
 * @date 2026-07-31 9:02
 */
public class MinimumPushes3016 {

    public int minimumPushes(String word) {
        int[] cnt = new int[26];
        for (char c : word.toCharArray()) {
            cnt[c - 'a']++;
        }
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) {
            q.offer(new int[]{i, cnt[i]});
        }
        int k = 0;
        int res = 0;
        for (int i = 0; i < 26; i++) {
            int[] e = q.poll();
            if (e[1] == 0) {
                break;
            }
            res += (k++ / 8 + 1) * e[1];
        }
        return res;
    }
}

性能

目标

给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：

• arr 中 第一个 元素必须为 1 。
• 任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。

你可以执行以下 2 种操作任意次：

• 减小 arr 中任意元素的值，使其变为一个 更小的正整数 。
• 重新排列 arr 中的元素，你可以以任意顺序重新排列。

请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。

示例 1：

输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。

示例 2：

输入：arr = [100,1,1000]
输出：3
解释：
一个可行的方案如下：
1. 重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ，满足所有条件。
arr 中最大元素为 3 。

示例 3：

输入：arr = [1,2,3,4,5]
输出：5
解释：数组已经满足所有条件，最大元素为 5 。

说明：

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

思路

有一个正整数数组 arr，可以将任意元素变成比它更小的正整数，也可以按任意顺序重新排列元素。需要将 arr 变成目标数组，使得第一个元素为 1，且相邻元素差的绝对值不超过 1。返回目标数组可能的最大值。

根据题目要求，第一个元素必须是 1，且相邻元素差的绝对值不超过 1，要使元素值变大只能 +1，且该元素只能由大于等于它的元素转化而来。

贪心策略，从小到大排序数组，遍历数组记录最大值，由于元素值都大于 0，都可以操作成 1，当元素值小于最大值时直接跳过，否则，将元素操作成最大值加一。越大的元素越晚操作，可以使最大值更大。

由于最大值不超过 n，可以将大于 n 的元素都视为 n，这样可以使用计数排序优化。

代码

/**
 * @date 2026-06-29 18:11
 */
public class MaximumElementAfterDecrementingAndRearranging1846 {

    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        int res = 0;
        for (int num : arr) {
            if (num <= res) {
                continue;
            }
            res++;
        }
        return res;
    }

}

性能

目标

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

注意：Tony 可以按任意顺序购买雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

你必须使用计数排序解决此问题。

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。

说明：

• costs.length == n
• 1 <= n <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= coins <= 10^8

思路

costs[i] 表示第 i 支雪糕的数量，求使用现金 coins 所能购买雪糕的最大数量。

贪心策略：优先购买价格较低的雪糕。使用计数排序记录每种价格的雪糕数量，从小到大遍历价格，累加当前所能购买的雪糕数量，如果超过剩余金额直接返回。

代码

/**
 * @date 2026-06-22 9:27
 */
public class MaxIceCream1833 {

    public int maxIceCream_v1(int[] costs, int coins) {
        int max = 0;
        for (int cost : costs) {
            max = Math.max(max, cost);
        }
        int[] cnt = new int[max + 1];
        for (int cost : costs) {
            cnt[cost]++;
        }
        int res = 0;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            if (coins < i) {
                return res;
            }
            int amount = Math.min(coins / i, cnt[i]);
            coins -= amount * i;
            res += amount;
        }
        return res;
    }

}

性能

目标

给定一个长度为 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;
    }
}

性能