Lemonade Change
Easy · greedy
A lemonade stand sells cups for £5 each. Customers queue up and are served in order. Each customer buys exactly one cup and pays with a single £5, £10 or £20 note: bills[i] is the note that customer i hands over.
The stand starts with no money at all, so change can only be given from the notes it has been paid by earlier customers (including the notes just handed over by customers already served). Every customer must receive the correct change, using the notes in the till.
Return true if every customer can be given the correct change, and false as soon as one cannot.
Examples
Example 1
Input: bills = [5, 5, 5, 10, 20]
Output: true
The £10 customer gets one £5 back. The £20 customer needs £15 back and gets a £10 and a £5.
Example 2
Input: bills = [5, 5, 10, 10, 20]
Output: false
After the two £10 customers the till holds two £10 notes and no £5, so the £20 customer cannot get £15 back.
Example 3
Input: bills = [10, 5]
Output: false
The first customer needs £5 back and the till is empty.
Constraints
- 1 <= len(bills) <= 10^4
- bills[i] is 5, 10 or 20.