柠檬水找零 图解题解

收钱找零，什么时候该返回 false

你在卖柠檬水，每杯五元。顾客排成一队，依次掏五元、十元或二十元付钱，你手上一开始一张零钱都没有。每收一张账单都要当场找零：收十元找回五元，收二十元找回十五元。只要中途有一位顾客找不开，就返回 false；全队都顺利找开返回 true。题面例子 bills=[5,5,5,5,10,20,5,5,5,20,10,5]，答案是 true。

收二十要找十五，手上有两种凑法

收五元最省心：它正好是一杯的价，不用找零，直接攒着。收十元也只有一条路——找回五元，从手上抽一张五给他；手上一张五都没有就当场卡死，返回 false。麻烦的是收二十元，要找回十五。如果手上既有十元又有五元，一张十加一张五正好是十五；如果十元用光了，三张五也能凑出十五。两种都够十五，那该先用哪一种？

为什么收二十优先用一张十来找

把两种钞票的用途摆开看：五元既能给收十元的顾客找零，也能给收二十元的顾客凑数，处处用得上；十元只在收二十元时能搭一张五用一次，用途窄得多。收二十元时手上如果有十元，就先把这张只能救急一次的十元花出去，留下更万能的五元应付后面——收二十优先动用那张十元、把灵活的五元攒着，正是这道找零题的贪心落点。反过来，若舍不得十元、先掏三张五，等下一位又收十元或二十元时，手里五元不够就找不开了。所以规则定死：收二十优先「10+5」，手上没十元才退用三张五，两样都缺就返回 false。全程只需记五元、十元两个张数，二十元收进来永远找不出去、记它也没用。

跟着题面这队顾客挨笔找一遍

手上记 five、ten 两个数，从 five=0、ten=0 开始。前四位都付五元，five 攒到 4。第 5 位付十元，抽一张五找他，变成 five=3、ten=1。第 6 位付二十元，手上十元、五元都有，优先「10+5」，扣成 five=2、ten=0。第 7、8、9 位又都付五元，five 回到 5。第 10 位付二十元，这回 ten=0，只能掏三张五，扣成 five=2。第 11 位付十元，抽一张五，变成 five=1、ten=1。第 12 位付五元，five=2。十二笔全找开，返回 true。

为什么一遍扫就够，容易错在哪

从头到尾只扫一遍 n 张账单，每张做的都是常数次判断和加减，时间 O(n)；自始至终只留 five、ten 两个整数，空间 O(1)。真正容易写错的是收二十那步：手上有十元却图省事先用三张五，会把万能的五提前耗光，后面遇到只能用五来找的账单就卡住；也有人顺手去记二十元收了几张，可二十元给谁都找不开、记了用不上。还有收十元时忘了先看手上有没有五，缺五却硬找也会算错——没有五就该当场返回 false。

Python

def lemonadeChange(bills):
    five = ten = 0          # 只需记 5 元、10 元张数
    for b in bills:
        if b == 5:
            five += 1         # 收 5：不找零，存起来
        elif b == 10:
            if five == 0: return False  # 没 5 找不开
            five -= 1; ten += 1         # 找 1 张 5
        else:                  # b == 20，要找 15
            if ten and five:   # 优先 10+5（省下万能的 5）
                ten -= 1; five -= 1
            elif five >= 3:    # 没 10 才用三张 5
                five -= 3
            else: return False
    return True

C++

bool lemonadeChange(vector<int>& bills){
    int five = 0, ten = 0;        // 只记 5 元、10 元张数
    for(int b : bills){
        if(b == 5) five++;          // 收 5：存起来
        else if(b == 10){
            if(five == 0) return false;  // 没 5 找不开
            five--; ten++;               // 找 1 张 5
        } else {                    // b == 20，找 15
            if(ten > 0 && five > 0){ ten--; five--; }   // 优先 10+5
            else if(five >= 3) five -= 3;               // 退用三张 5
            else return false;
        }
    }
    return true;
}

Java

public boolean lemonadeChange(int[] bills) {
    int five = 0, ten = 0;        // 只记 5 元、10 元张数
    for (int b : bills) {
        if (b == 5) {
            five++;                 // 收 5：存起来
        } else if (b == 10) {
            if (five == 0) return false;  // 没 5 找不开
            five--; ten++;                // 找 1 张 5
        } else {                    // b == 20，找 15
            if (ten > 0 && five > 0) { ten--; five--; }  // 优先 10+5
            else if (five >= 3) { five -= 3; }           // 退用三张 5
            else return false;
        }
    }
    return true;
}