。柠檬水变化

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

以上是。柠檬水变化的详细内容。更多信息请关注PHP中文网其他相关文章！