题目描述
思路解析
一句话答案：LeetCode 860 柠檬水找零：靠贪心只攒五元和十元两种张数，收二十优先用「10+5」找零、把更万能的五元省下来，凑不出就返回 false，一遍扫完时间 O(n)、空间 O(1)。
收钱找零，什么时候该返回 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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句「只盯 5 元和 10 元张数；收 20 优先用 10+5 找零，省下更万能的 5 元，不够再掏三张 5」——下面每一帧都在套它。20 元收进来只入箱、不参与任何找零。
把顾客的账单序列摆成一排（这就是动画主体）。开局你手上空空：5 元 0 张、10 元 0 张。紫色高亮的是当前正要处理的这张账单，从最左边第 1 位顾客开始。
第 1 位顾客付 5 元。5 元正好是一杯柠檬水的价，不用找零，直接把这张 5 攒进手里（5 元最万能，多多益善）。手上零钱变为 手上 5 元 × 1，10 元 × 0。
第 2 位顾客付 5 元。5 元正好是一杯柠檬水的价，不用找零，直接把这张 5 攒进手里（5 元最万能，多多益善）。手上零钱变为 手上 5 元 × 2，10 元 × 0。
第 3 位顾客付 5 元。5 元正好是一杯柠檬水的价，不用找零，直接把这张 5 攒进手里（5 元最万能，多多益善）。手上零钱变为 手上 5 元 × 3，10 元 × 0。
第 4 位顾客付 5 元。5 元正好是一杯柠檬水的价，不用找零，直接把这张 5 攒进手里（5 元最万能，多多益善）。手上零钱变为 手上 5 元 × 4，10 元 × 0。
第 5 位顾客付 10 元。收 10 元要找回 5 元，从手上抽 1 张 5 找给他，再把这张 10 收下。手上零钱变为 手上 5 元 × 3，10 元 × 1。
第 6 位顾客掏 20 元，你得找回 15。此刻手上有 10 元，按贪心优先用「10 + 5」这一种找法——因为 5 元既能找 10 又能找 20、更万能，能省则省。下一帧落定扣钱。
落定：从手上拿掉 1 张 10 和 1 张 5 找给顾客，这张 20 收进箱子（注意它以后永远帮不上找零）。手上零钱更新为 手上 5 元 × 2，10 元 × 0，继续下一位。
第 7 位顾客付 5 元。5 元正好是一杯柠檬水的价，不用找零，直接把这张 5 攒进手里（5 元最万能，多多益善）。手上零钱变为 手上 5 元 × 3，10 元 × 0。
第 8 位顾客付 5 元。5 元正好是一杯柠檬水的价，不用找零，直接把这张 5 攒进手里（5 元最万能，多多益善）。手上零钱变为 手上 5 元 × 4，10 元 × 0。
第 9 位顾客付 5 元。5 元正好是一杯柠檬水的价，不用找零，直接把这张 5 攒进手里（5 元最万能，多多益善）。手上零钱变为 手上 5 元 × 5，10 元 × 0。
第 10 位顾客掏 20 元，你得找回 15。此刻手上没有 10 元，只好退一步，用「三张 5」凑齐 15 找出去。下一帧落定扣钱。
落定：从手上拿掉 3 张 5 找给顾客，这张 20 收进箱子（注意它以后永远帮不上找零）。手上零钱更新为 手上 5 元 × 2，10 元 × 0，继续下一位。
第 11 位顾客付 10 元。收 10 元要找回 5 元，从手上抽 1 张 5 找给他，再把这张 10 收下。手上零钱变为 手上 5 元 × 1，10 元 × 1。
第 12 位顾客付 5 元。5 元正好是一杯柠檬水的价，不用找零，直接把这张 5 攒进手里（5 元最万能，多多益善）。手上零钱变为 手上 5 元 × 2，10 元 × 1。
一整队顾客扫下来，靠「只盯 5 元和 10 元张数 + 收 20 优先用 10+5」这套贪心，每一笔都正好找得开，全部账单变灰表示处理完成。返回 true。
边界先想清：第一位若付 10 或 20、手上没零钱必然 false；只有 5 元攒得够，后面的 10、20 才找得开。
两个高频追问：20 元永远没法找零所以不必记；收 20 优先 10+5 是「不堵后路」的局部最优，逐步最优拼出整体最优。
参考代码
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复杂度
- 时间：O(n)，只扫一遍 n 张账单，每张常数时间判断与计数
- 空间：O(1)，只用 five / ten 两个整数变量
易错点
面试追问把动画讲成自己的话
追问为什么全程不用记 20 元的张数？
追问这题贪心为什么一定对、不会因小失大？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组的相对排序
LeetCode 1122 · 简单 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题