577. Change at the Stall
A juice stall sells every drink for exactly 5 coins. Customers queue up in the order given by bills, and each customer pays with a single note worth 5, 10 or 20 coins and buys exactly one drink. The vendor starts the day with an empty cash box, and must hand back the correct change immediately, using only notes received from earlier customers.
Return true if the vendor can give correct change to every customer in the queue, otherwise false. When paying with 20, the vendor owes 15 in change and may give either one 10 and one 5, or three 5 notes. Choose the way that keeps the most flexibility for later customers.
A single pass with two counters, O(n) time and O(1) space, is enough.
Example 1
- Input:
- bills = [5,5,10,20]
- Output:
- true
- Explanation:
Two 5 notes are collected, the 10 is changed with a 5, and the 20 is changed with the remaining 10 and 5.
Example 2
- Input:
- bills = [5,10,10]
- Output:
- false
- Explanation:
After the first 10 the vendor has no 5 note left, so the second 10 cannot be changed.
Example 3
- Input:
- bills = [5,5,10,5,20,5,5,5,20]
- Output:
- true
- Explanation:
The first 20 is changed with a 10 and a 5, and the second 20 is changed with three 5 notes, so everyone is served.
Constraints
1 ≤ bills.length ≤ 100000bills[i]is one of5,10,20
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)