LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.21
• 题目：1833. 雪糕的最大数量
• 难度：中等
• 标签：数组、计数排序、贪心

1. 题目理解

问题描述： 给定雪糕价格数组 costs 和现金 coins，想要购买尽可能多的雪糕，优先买便宜的；要求使用计数排序思路解题，返回最多能购买的雪糕数量。

示例：

输入：costs = [1,3,2,4,1], coins = 7 输出：4 解释：依次购买价格1、1、2、3，总花费7，共4支。

2. 解题思路

核心观察

1. 要买到最多雪糕，贪心策略：从小到大购买。
2. 普通快排 $O(n\log n)$，题目要求计数排序，价格范围 1~100000，可开计数数组统计每种价格雪糕数量。
3. 从小到大遍历价格，批量扣除对应价格开销，统计购买数量，钱不足直接返回结果。

算法步骤

1. 创建计数数组统计每个价格出现次数；
2. 从小到大遍历价格 i：
   • 剩余现金不够单支 i，直接返回已购买总数；
   • 循环购买当前价格所有雪糕，每买一支扣钱、计数+1；
   • 中途钱不足立刻返回答案；
3. 全部遍历完成返回总数。

3. 代码实现

package lc1800_lc1899.lc1833;

import java.util.Arrays;

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int cur=costs[0];
        int index=0;
        int count = 0;
        while (coins>cur){
            coins-=costs[index++];
            count++;
        }
        return count;
    }
}

4. 代码优化说明

class Solution {
public int maxIceCream(int[] costs, int coins) {
    // 计数数组，题目价格上限100000
    int[] counts = new int[100001];
    // 统计每种价格雪糕的数量
    for (int cost : costs) {
        counts[cost] ++;
    }
    int ans = 0;
    // 从小到大遍历价格，贪心优先买低价雪糕
    for (int i = 1; i < 100001; i++) {
        // 连单支都买不起，直接退出
        if (coins < i) {
            return ans;
        }
        // 逐个购买当前价格全部雪糕
        for (int j = 0; j < counts[i]; j++) {
            coins -= i;
            ans ++;
            // 购买后剩余现金不足下一支，提前返回
            if (coins < i) {
                return ans;
            }
        }
    }
    return ans;
}
}

5. 复杂度分析

• 普通排序贪心版 时间：$O(n\log n)$，排序开销大 空间：$O(\log n)$ 排序栈开销
• 计数排序优化版 时间：$O(n+C)$，C=100000价格上限，线性复杂度，符合题目计数排序要求 空间：$O(C)$ 固定大小计数数组，常数上限

6. 总结

• 核心贪心：想要数量最多，必须优先选购单价最低的雪糕。
• 优化亮点：使用计数排序替代普通快排，降低时间复杂度，符合题目强制要求；价格有序遍历，提前剪枝减少无效循环。
• 关键约束：题目明确要求使用计数排序，不能直接调用Arrays.sort。