LeetCode 每日一题笔记 日期：2026.06.01 题目：2144. 打折购买糖果的最小开销

LeetCode 每日一题笔记0. 前言日期2026.06.01题目2144. 打折购买糖果的最小开销难度简单标签贪心、排序、优先队列1. 题目理解问题描述商店打折规则每购买2个糖果可免费获赠1个糖果。免费糖果的价格必须小于等于购买的两个糖果价格的较小值。给定糖果价格数组cost求获得所有糖果的最小总开销。示例输入cost [1,2,3]输出5解释购买价格为2和3的糖果可免费获得价格为1的糖果总开销为 2 3 5。2. 解题思路核心观察为了让总开销最小需要让最贵的糖果被免费赠送。策略按价格从高到低排序每三个糖果为一组前两个付费第三个免费。算法步骤将糖果价格按升序排序从后往前遍历每三个为一组前两个计入开销第三个跳过遍历结束返回总开销。3. 代码实现packagelc2144;importjava.util.Arrays;classSolution{publicintminimumCost(int[]cost){intres0;Arrays.sort(cost);intncost.length;intcount0;for(intin-1;i0;i--){if(count!2){rescost[i];count;}else{count0;}}returnres;}}4. 代码优化说明代码未做任何修改仅添加注释讲解classSolution{publicintminimumCost(int[]cost){// 定义一个大顶堆让价格从高到低排列PriorityQueueIntegerpqnewPriorityQueue((a,b)-b-a);// 将所有糖果价格加入堆中for(intc:cost){pq.offer(c);}intres0;// 当堆中还有3个及以上糖果时执行“买二送一”while(pq.size()3){respq.poll();// 买最贵的计入开销respq.poll();// 买第二贵的计入开销pq.poll();// 第三件免费直接跳过}// 处理剩下不足3个的糖果全部购买while(!pq.isEmpty()){respq.poll();}returnres;}}5. 复杂度分析排序贪心解法时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)排序占主要开销遍历为线性。空间复杂度O(1)O(1)O(1)原地排序不考虑排序栈开销仅用常数变量。优先队列解法时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)建堆和出堆操作均为O(nlog⁡n)O(n \log n)O(nlogn)。空间复杂度O(n)O(n)O(n)优先队列存储所有糖果价格。6. 总结核心贪心策略通过让高价糖果被免费赠送来最小化开销。两种解法均基于“每三个一组前两个付费”的思想排序法实现更简洁优先队列法更直观。关键从高到低处理糖果确保免费赠送的是尽可能贵的糖果。