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