LC 1833. 雪糕的最大数量

题目描述

这是 LeetCode 上的 1833. 雪糕的最大数量 ，难度为 中等。

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

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。

Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

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

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

示例 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], 

输出：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$

---

基本分析

从题面看，是一道「01 背包」问题，每个物品的成本为 $cost[i]$，价值为 $1$。

但「01 背包」的复杂度为 $O(N\times C)$，其中 $N$ 为物品数量（数量级为 $10^5$），$C$ 为背包容量(数量级为 $10^8$)。显然会 TLE。

换个思路发现，每个被选择的物品对答案的贡献都是 $1$，优先选择价格小的物品会使得我们剩余金额尽可能的多，将来能够做的决策方案也就相应变多。

因此一个直观的做法是，对物品数组进行「从小到大」排序，然后「从前往后」开始决策购买。

---

证明

直观上，这样的贪心思路可以使得最终选择的物品数量最多。

接下来证明一下该思路的正确性。

假定贪心思路取得的序列为 $[a1,a2,a3,…,an]$（长度为 $n$），真实最优解所取得的序列为 $[b1,b2,b3,..,bm]$（长度为 $m$）。

两个序列均为「单调递增序列」。

其中最优解所对应具体方案不唯一，即存在多种选择方案使得物品数量相同。

因此，我们只需要证明两个序列长度一致即可。

按照贪心逻辑，最终选择的方案总成本不会超过 $coins$，因此至少是一个合法的选择方案，天然有 $n \leq m$，只需要证明 $n \geq m$ 成立，即可得证 $n = m$。

通过反证法证明 $n \geq m$ 成立，假设 $n \geq m$ 不成立，即有 $n < m$。

根据贪心决策，我们选择的物品序列在「排序好的 $cost$ 数组」里，必然是一段连续的前缀。并且再选择下一物品将会超过总费用 $coins$；而真实最优解的选择方案在「排序好的 $cost$ 数组」里分布不定。

这时候我们可以利用「每个物品对答案的贡献均为 $1$，将最优解中的分布靠后的物品，替换为分布较前的物品，不会使得费用增加，同时答案不会变差」。

从而将真实最优解也调整为某段连续的前缀。

综上，通过反证法得证 $n \geq m$ 成立，结合 $n \leq m$，可推出 $n = m$。

即贪心解必然能够取得与最优解一样的长度。

---

贪心

排序，从前往后决策，直到不能决策为止。

Java 代码：

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int n = costs.length;
        Arrays.sort(costs);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (coins >= costs[i]) {
                ans++; coins -= costs[i];
            }
        }
        return ans;
    }
}

Python 代码：

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()
        ans = 0
        for i in range(len(costs)):
            if coins >= costs[i]:
                ans += 1
                coins -= costs[i]
        return ans

C++ 代码：

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        int n = costs.size();
        sort(costs.begin(), costs.end());
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (coins >= costs[i]) {
                ans++; coins -= costs[i];
            }
        }
        return ans;
    }
};

TypeScript 代码：

function maxIceCream(costs: number[], coins: number): number {
    costs.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < costs.length; i++) {
        if (coins >= costs[i]) {
            ans++; coins -= costs[i];
        }
    }
    return ans;
};

• 时间复杂度：排序复杂度为 $O(n\log{n})$；获取答案的复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：排序复杂度为 $O(\log{n})$。整体复杂度为 $O(\log{n})$

PS. 这里假定 Arrays.sort 使用的是「双轴排序」的实现。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1833 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。