LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.01
• 题目：2144. 打折购买糖果的最小开销
• 难度：简单
• 标签：贪心、排序、优先队列

1. 题目理解

问题描述： 商店打折规则：每购买2个糖果，可免费获赠1个糖果。免费糖果的价格必须小于等于购买的两个糖果价格的较小值。给定糖果价格数组 cost，求获得所有糖果的最小总开销。

示例：

输入：cost = [1,2,3] 输出：5 解释：购买价格为2和3的糖果，可免费获得价格为1的糖果，总开销为 2 + 3 = 5。

2. 解题思路

核心观察

• 为了让总开销最小，需要让最贵的糖果被免费赠送。
• 策略：按价格从高到低排序，每三个糖果为一组，前两个付费，第三个免费。

算法步骤

1. 将糖果价格按升序排序；
2. 从后往前遍历，每三个为一组，前两个计入开销，第三个跳过；
3. 遍历结束，返回总开销。

3. 代码实现

package lc2144;

import java.util.Arrays;

class Solution {
    public int minimumCost(int[] cost) {
        int res = 0;
        Arrays.sort(cost);
        int n = cost.length;
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (count != 2) {
                res += cost[i];
                count++;
            } else {
                count = 0;
            }
        }
        return res;
    }
}

4. 代码优化说明

（代码未做任何修改，仅添加注释讲解）

class Solution {
public int minimumCost(int[] cost) {
    // 定义一个大顶堆，让价格从高到低排列
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    // 将所有糖果价格加入堆中
    for (int c : cost) {
        pq.offer(c);
    }
    int res = 0;
    // 当堆中还有3个及以上糖果时，执行“买二送一”
    while (pq.size()>=3) {
        res += pq.poll(); // 买最贵的（计入开销）
        res += pq.poll(); // 买第二贵的（计入开销）
        pq.poll(); // 第三件免费，直接跳过
    }
    // 处理剩下不足3个的糖果，全部购买
    while (!pq.isEmpty()) {
        res += pq.poll();
    }
    return res;
}
}

5. 复杂度分析

• 排序贪心解法
  • 时间复杂度：$O(n\log n)$，排序占主要开销，遍历为线性。
  • 空间复杂度：$O(1)$，原地排序（不考虑排序栈开销），仅用常数变量。
• 优先队列解法
  • 时间复杂度：$O(n\log n)$，建堆和出堆操作均为 $O(n\log n)$。
  • 空间复杂度：$O(n)$，优先队列存储所有糖果价格。

6. 总结

• 核心：贪心策略，通过让高价糖果被免费赠送来最小化开销。
• 两种解法均基于“每三个一组，前两个付费”的思想，排序法实现更简洁，优先队列法更直观。
• 关键：从高到低处理糖果，确保免费赠送的是尽可能贵的糖果。