带你读《图解算法小抄》二十二、贪心算法（3）

带你读《图解算法小抄》二十二、贪心算法（2）https://developer.aliyun.com/article/1347852?groupCode=tech_library

3.柠檬水变化

1）题目描述

给定一个整数数组 bills，表示顾客购买柠檬水的账单金额。柠檬水的价格为 5 美元。每个顾客只会购买一杯柠檬水，并且顾客只能支付 5、10 或 20 美元的钞票。顾客按顺序购买柠檬水，且每次购买都会给出一张钞票。判断你能否正确找零。

如果你手头没有足够的零钱找零，或者无法正确找零，则返回 false。否则，返回 true。

2）解题步骤

为了解决柠檬水找零问题，我们可以使用贪心算法来解决。

贪心算法的思路是尽量用面额大的钞票找零。我们遵循以下策略：

• 维护两个变量 five 和 ten，分别表示手中的 5 美元和 10 美元的数量。
  
• 遍历账单数组 bills，对于每个账单金额 bill：
  
• 如果 bill 为 5 美元，不需要找零，将 five 增加 1。
  
• 如果 bill 为 10 美元，需要找零 5 美元，首先检查是否有足够的 5 美元，如果没有，则无法找零，返回 false；否则，将 five 减少 1，将 ten 增加 1。
  
• 如果 bill 为 20 美元，需要找零 15 美元，首先检查是否有足够的零钱找零。我们有两种选择：
  
• 一种是找零 1 张 10 美元和 1 张 5 美元。如果有足够的 10 美元和 5 美元，将 ten 减少 1，five 减少 1；
  
• 另一种是找零 3 张 5 美元。如果有足够的 5 美元，将 five 减少 3。
  
• 如果以上两种方式都无法满足找零条件，则无法找零，返回 false。
  
• 遍历结束后，如果能够正确找零，则返回 true。
  

以下是使用贪心算法解决柠檬水找零问题的算法框架：

function lemonadeChange(bills) {
  let five = 0;
  let ten = 0;  for (let i = 0; i < bills.length; i++) {
    if (bills[i] === 5) {
      five++;
    } else if (bills[i] === 10) {
      if (five === 0) {
        return false;
      }
      five--;
      ten++;
    } else if (bills[i] === 20) {
      if (ten > 0 && five > 0) {
        ten--;
        five--;
      } else if (five >= 3) {
        five -= 3;
      } else {
        return false;
      }
    }
  }
  return true;
}

带你读《图解算法小抄》二十二、贪心算法（4）https://developer.aliyun.com/article/1347850?groupCode=tech_library