雪糕的最大数量 图解题解

这道题到底在问什么

输入

costs=[1,3,2,4,1], coins=7

输出

4

输入

costs=[10,6,8,7,7,8], coins=5

输出

0

输入

costs=[1,6,3,1,2,5], coins=20

输出

6

最优解：一步一步想明白

1. 3记牢一句:先把价格从小到大排序,从最便宜的一支支买,买得起(coins ≥ c)就买下 count 加一,轮到买不起的那支就停,count 即答案。下面每帧都在套这句。
2. 4先看清画面。上面是原始价格 [1,3,2,4,1],第 i 格就是第 i 支雪糕的价格,顺序是乱的。右边这块购买状态记着我们最关心的三个量:剩余现金此刻是 7 元,已买 0 支,一分钱还没花。要买到最多支数,第一件事是把价格排好序,让便宜的排在前面。
3. 5把价格从小到大排成 [1,1,2,3,4]。为什么要从便宜的开始?因为目标是支数最多,不是省钱本身,而是让每一块钱换回尽量多的雪糕。同样一笔钱,先买便宜的能换到更多支。要是先花大价钱抢那支 4 元的,后面本可以买好几支便宜的机会就被挤掉了。排好序,现金还是 7 元,准备从最左边这支 1 元开始一支支买。
4. 6正式开买之前把起点钉牢。现在一支雪糕都还没买,手里 7 元原封不动,已买支数 count 等于 0。接下来从最便宜的那支起,一支支往贵的方向走,买得起就买、现金减价格、count 加一,直到遇上一支买不起的为止。目标是尽量多买几支。
5. 7盯住最左边这支待考察的雪糕,记住贯穿全程的那把尺子。每一步只问一句:手里剩的现金够不够付它的价格?只要剩余现金大于等于当前价格 c,就买得起,买下它,现金扣掉 c、count 加一。一旦剩的钱比当前这支还少,连排在最前的最便宜一支都付不起,那后面更贵的更别想,直接停。下面就拿这把尺子从 1 元那支一支支量过去。
6. 8轮到最便宜的第 1 支,价格是 1 元。此刻还没买任何雪糕,手里 7 元。先把它拎出来,看看手里这 7 元付不付得起这 1 元。
7. 9拿尺子一量:手里 7 元,大于等于这支的 1 元,买得起。既然付得起,就没有理由不买,毕竟每多买一支都是赚。把它买下来。
8. 10把这支 1 元雪糕正式买下(标绿)。现金从 7 元付掉 1 元,剩 6 元;已买支数从 0 加到 1 支。接着看下一支更贵一点的。
9. 11轮到第 2 支,价格是 1 元。前面 1 支已经买下(蓝色),现金花到只剩 6 元,已买 1 支。先把它拎出来,看看手里这 6 元付不付得起这 1 元。
10. 12拿尺子一量:手里 6 元,大于等于这支的 1 元,买得起。既然付得起,就没有理由不买,毕竟每多买一支都是赚。把它买下来。
11. 13把这支 1 元雪糕正式买下(标绿)。现金从 6 元付掉 1 元,剩 5 元;已买支数从 1 加到 2 支。接着看下一支更贵一点的。
12. 14轮到第 3 支,价格是 2 元。前面 2 支已经买下(蓝色),现金花到只剩 5 元,已买 2 支。先把它拎出来,看看手里这 5 元付不付得起这 2 元。
13. 15拿尺子一量:手里 5 元,大于等于这支的 2 元,买得起。既然付得起,就没有理由不买,毕竟每多买一支都是赚。把它买下来。
14. 16把这支 2 元雪糕正式买下(标绿)。现金从 5 元付掉 2 元,剩 3 元;已买支数从 2 加到 3 支。接着看下一支更贵一点的。
15. 17轮到第 4 支,价格是 3 元。前面 3 支已经买下(蓝色),现金花到只剩 3 元,已买 3 支。先把它拎出来,看看手里这 3 元付不付得起这 3 元。
16. 18拿尺子一量:手里 3 元,大于等于这支的 3 元,买得起。注意这里现金和价格正好相等,3 元付 3 元刚好花光,这一支照样买得起、要算进去,这正是判定用大于等于、把等号取到的地方。把它买下来。
17. 19把这支 3 元雪糕正式买下(标绿)。现金从 3 元付掉 3 元,正好全部花光;已买支数从 3 加到 4 支。接着看下一支更贵一点的。
18. 20轮到第 5 支,价格是 4 元。前面 4 支已经买下(蓝色),现金已经花光,已买 4 支。先把它拎出来,看看手里已经一分不剩,还付不付得起这 4 元。
19. 21拿尺子一量:手里的现金已经一分不剩,却要付 4 元,钱不够,这支买不起(标红)。前面 4 支便宜的已经把现金花得差不多了,轮到这支就付不起了。
20. 22为什么这支买不起就能直接停,不用再看后面?因为价格已经从小到大排好,这支 4 元正是剩下里最便宜、也是唯一没买的一支(已标红)。连它都付不起,后面就算还有更贵的雪糕也一定买不起。所以到此为止,能买到的最大支数就锁定在 4 支。
21. 23回头验证一下这个答案。买下最便宜的前 4 支,价格是 1、1、2、3,一共 7 元,正好等于手里的 7 元,现金正好全部花光。剩下那支 4 元的(标红)确实买不起。想再多买一支是不可能的,因为便宜的都已经买光了,答案就是 4 支。
22. 24回看整条路:先把价格排成 [1,1,2,3,4],从最便宜的一支支买。1 元买下、又一个 1 元买下、2 元买下、3 元买下,现金正好花光,买到 4 支;轮到 4 元那支时钱不够,停手。整道题的窍门就一句:先排序,再从便宜到贵地买,买得起就买、买不起就停。最终答案 4。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()
        for i, c in enumerate(costs):
            if coins < c:
                return i
            coins -= c
        return len(costs)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(), costs.end());
        int n = costs.size();
        for (int i = 0; i < n; ++i) {
            if (coins < costs[i]) return i;
            coins -= costs[i];
        }
        return n;
    }
};

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

复杂度

面试官可能追问