860。檸檬水變化

難度：簡單

主題： 數組，貪婪

在檸檬水攤上，每杯檸檬水售價 5 美元。顧客排隊向您購買，並一次訂購一件（按照帳單指定的順序）。每位顧客只能購買一份檸檬水，並以 5 美元、10 美元或 20 美元的鈔票付款。您必須向每位客戶提供正確的零錢，以便客戶支付 5 美元作為淨交易。

注意您一開始手邊沒有零錢。

給定一個整數數組bills，其中bills[i] 是第i ^個 客戶支付的賬單，如果您能為每個客戶提供正確的零錢，則返回true，否則返回false .

範例1：

• 輸入： 帳單 = [5,5,5,10,20]
• 輸出： true
• 解釋：
  • 從前 3 位顧客中，我們按順序收取三張 5 美元的鈔票。
  • 我們從第四位顧客收取 10 美元的鈔票並返還 ​​5 美元。
  • 從第五位顧客開始，我們給了一張 10 美元和一張 5 美元的鈔票。
  • 由於所有客戶都得到了正確的零錢，我們輸出 true。

範例2：

• 輸入： 帳單 = [5,5,10,10,20]
• 輸出： false
• 解釋：
  • 我們從前兩位顧客中收取兩張 5 美元的鈔票。
  • 對於接下來的兩位顧客，我們收取 10 美元的鈔票並返還 ​​5 美元的鈔票。
  • 對於最後一位顧客，我們無法退還 15 美元的零錢，因為我們只有兩張 10 美元的鈔票。
  • 由於並非每個客戶都收到了正確的找零，所以答案是錯誤的。

約束：

• 5
• bills[i] 為 5、10 或 20。

解決方案：

我們需要模擬根據客戶用來支付的帳單向客戶提供找零的過程。關鍵是追蹤您擁有的 5 美元和 10 美元鈔票的數量，因為需要這些鈔票來為更大的鈔票找零

讓我們用 PHP 實作這個解決方案：860。檸檬水變化

解釋：

1. 初始化：我們首先將 $5 和 $10 設為 0，代表我們擁有的 5 美元和 10 美元鈔票的數量。

2. 處理每張帳單:

   • 如果客戶用 5 美元的鈔票付款：我們只需增加 5 美元鈔票的數量。
   • 如果客戶用 10 美元鈔票付款：我們需要找回一張 5 美元鈔票作為找零，因此我們減少 5 美元鈔票的數量並增加 10 美元鈔票的數量。如果我們沒有 5 美元鈔票，則返回 false。
   • 如果客戶用 20 美元的鈔票付款：我們優先提供一張 10 美元鈔票和一張 5 美元鈔票作為找零。如果不可能，我們會嘗試贈送三張 5 美元的鈔票。如果兩個選項都不可用，則傳回 false。

3. 最終檢查：如果我們已成功處理所有客戶且沒有用完零錢，則返回 true。

邊緣情況：

• 該函數應該處理無法正確找零的情況，例如當您過早收到 10 美元或 20 美元的鈔票而手頭沒有必要的 5 美元鈔票時。
• 由於限制（最多 100,000 個客戶），它應該有效地處理大輸入量。此解決方案的運行時間複雜度為 O(n)，使其成為該問題的最佳解決方案。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給存儲庫 一顆星，或者在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub