🔗 🟢 860. Lemonade Change 1286

tags: Weekly Contest 91 陣列(Array) 貪心(Greedy) 模擬(Simulation)

題意

你有一個檸檬水攤位，每杯檸檬水賣 55 元。顧客們按照順序排隊購買你的檸檬水，每次按順序點一杯檸檬水（按訂單指定的順序）。

每個顧客只買一杯檸檬水，並且每位顧客都會付 55 元、1010 元或 2020 元的硬幣。

給定一個整數陣列 billsbills ，其中 bills[i]bills[i] 是第 ii 位顧客支付的硬幣，如果你能為每位顧客提供正確的找零，則返回 truetrue，否則返回 falsefalse。

注意：一開始你手上沒有任何硬幣。

思路：貪心(Greedy)

首先分類討論三種情況：

  1. 顧客支付 55 元，我們不需要找零。
  2. 顧客支付 1010 元，我們需要找 11 個 55 元給顧客。
  3. 顧客支付 2020 元，此時可以找 11 個 1010 元和 11 個 55 元硬幣、或 33 個 55 元硬幣。
    • 如果有 1010 元硬幣，則應優先找 1010 元硬幣，因為在總金額不變的情況下，保留 55 元硬幣可以有更高的彈性。
    • 如果沒有 1010 元硬幣，則只能找 33 個 55 元硬幣。

注意到我們不會使用到 2020 元硬幣，因此只需要維護 55 元硬幣和 1010 元硬幣的數量即可。

在找零時可以先假設有足夠的 55 元硬幣，這樣可以把檢查移到找零後，使得程式碼較為整潔。若找零後 55 元硬幣的數量為負數，則代表無法找零，直接返回 falsefalse。

複雜度分析

  • 時間複雜度：O(n)O(n)，其中 nn 為顧客數量。
  • 空間複雜度：O(1)O(1)，只需要常數空間來儲存硬幣數量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        cnt5 = cnt10 = cnt20 = 0 # 硬幣數量
        for x in bills: # 支付的方式
            if x == 5: # 5元
                cnt5 += 1
            elif x == 10: # 10元
                cnt10 += 1
                cnt5 -= 1
            else: # 20元
                # cnt20 += 1 # 實際上不需要紀錄 20 元的數量
                if cnt10 > 0: # 如果有10元，就先找10元
                    cnt10 -= 1
                    cnt5 -= 1
                else: # 如果沒有10元，就找3個5元
                    cnt5 -= 3
            if cnt5 < 0: # 5 元硬幣不夠用，無法找零
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int cnt5 = 0, cnt10 = 0;
        for (int x : bills) {
            if (x == 5) {
                cnt5++;
            } else if (x == 10) {
                cnt10++;
                cnt5--;
            } else {
                if (cnt10 > 0) {
                    cnt10--;
                    cnt5--;
                } else {
                    cnt5 -= 3;
                }
            }
            if (cnt5 < 0) {
                return false;
            }
        }
        return true;
    }
};

寫在最後

Cover photo is remixed from @吃肥皂泡泡, thanks for their work!