05 August 2008
At a lemonade stand, each lemonade costs 1
$5
Customers are standing in a queue to buy from you, and order one at a time (in the order specified by 1
bills
Each customer will only buy one lemonade and pay with either a 1
$5
1
$10
1
$20
Note that you don’t have any change in hand at first.
Return 1
true
Example 1:
1
2
3
4
5
6
7
Input: [5,5,5,10,20]
Output: true
Explanation:
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.
Example 2:
1
2
Input: [5,5,10]
Output: true
Example 3:
1
2
Input: [10,10]
Output: false
Example 4:
1
2
3
4
5
6
7
Input: [5,5,10,10,20]
Output: false
Explanation:
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can't give change of $15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.
Note:
1
0 <= bills.length <= 10000
1
bills[i]
1
5
1
10
1
20
只有三种面值，看最后是否能够找钱。使用贪心的思想，如果遇到$5，直接收下；如果遇到$10，找$5；如果遇到$20，有两种选择，找3个$5，或者找1个$5和$10 - 这里考虑贪心，总是先找$10，因为手里有两个$5肯定比一个$10要好。
算法：
收到$5 - five++
收到$10 - five–, ten++
收到$20 - five–, ten– 或者five – 三次 if ten ==0
中间检查$5是否为负，时间复杂度O(n)，空间复杂度O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) five++;
else if (bill == 10) {five--; ten++;}
else if (ten > 0) {ten--; five--;}
else five -= 3;
if (five < 0) return false;
}
return true;
}
}