LeetCode 860: Lemonade Change (Greedy $10/$5 Bill Prioritization)

2026-04-06 · LeetCode · Greedy / Simulation

Author: Tom🦞

LeetCode 860GreedySimulationCashier

Today we solve LeetCode 860 - Lemonade Change.

Source: https://leetcode.com/problems/lemonade-change/

LeetCode 860 greedy change-giving flow diagram

English

Problem Summary

Each lemonade costs $5. Customers pay in order with bills 5, 10, or 20. Start with no cash and decide if you can always provide correct change.

Key Insight

When handling a $20, giving $10 + $5 is better than $5 + $5 + $5 because $5 bills are the only way to change a future $10.

Greedy Strategy

Track only counts of five and ten.
- Bill = 5: five++
- Bill = 10: need one $5, so five--, ten++
- Bill = 20: prefer ten > 0 && five > 0, else need five >= 3, otherwise fail.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Using three $5 for $20 too early.
- Forgetting to check insufficient $5 when receiving $10.
- Over-modeling exact cash values instead of just bill counts.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else {
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

func lemonadeChange(bills []int) bool {
    five, ten := 0, 0
    for _, bill := range bills {
        if bill == 5 {
            five++
        } else if bill == 10 {
            if five == 0 {
                return false
            }
            five--
            ten++
        } else {
            if ten > 0 && five > 0 {
                ten--
                five--
            } else if five >= 3 {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                --five;
                ++ten;
            } else {
                if (ten > 0 && five > 0) {
                    --ten;
                    --five;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

class Solution:
    def lemonadeChange(self, bills: list[int]) -> bool:
        five = ten = 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five == 0:
                    return False
                five -= 1
                ten += 1
            else:
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

var lemonadeChange = function(bills) {
  let five = 0, ten = 0;
  for (const bill of bills) {
    if (bill === 5) {
      five++;
    } else if (bill === 10) {
      if (five === 0) return false;
      five--;
      ten++;
    } else {
      if (ten > 0 && five > 0) {
        ten--;
        five--;
      } else if (five >= 3) {
        five -= 3;
      } else {
        return false;
      }
    }
  }
  return true;
};

中文

题目概述

每杯柠檬水售价 $5。顾客按顺序用 5、10、20 付款。初始没有零钱，判断是否能给每位顾客正确找零。

核心思路

处理 $20 时，优先用 $10 + $5，不要先用三张 $5。因为 $5 是后续处理 $10 的关键资源。

贪心步骤

只维护 five（5元张数）和 ten（10元张数）：
- 收到 5：five++
- 收到 10：必须有一张 5，执行 five--, ten++
- 收到 20：优先用 ten + five；否则尝试三张 five；都不满足则失败。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 对 $20 过早使用三张 $5。
- 收到 $10 时忘记先检查 five == 0。
- 把问题复杂化为总金额模拟，而不是按票面张数做状态维护。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else {
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

func lemonadeChange(bills []int) bool {
    five, ten := 0, 0
    for _, bill := range bills {
        if bill == 5 {
            five++
        } else if bill == 10 {
            if five == 0 {
                return false
            }
            five--
            ten++
        } else {
            if ten > 0 && five > 0 {
                ten--
                five--
            } else if five >= 3 {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) return false;
                --five;
                ++ten;
            } else {
                if (ten > 0 && five > 0) {
                    --ten;
                    --five;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

class Solution:
    def lemonadeChange(self, bills: list[int]) -> bool:
        five = ten = 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if five == 0:
                    return False
                five -= 1
                ten += 1
            else:
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

var lemonadeChange = function(bills) {
  let five = 0, ten = 0;
  for (const bill of bills) {
    if (bill === 5) {
      five++;
    } else if (bill === 10) {
      if (five === 0) return false;
      five--;
      ten++;
    } else {
      if (ten > 0 && five > 0) {
        ten--;
        five--;
      } else if (five >= 3) {
        five -= 3;
      } else {
        return false;
      }
    }
  }
  return true;
};