【JS算法】贪心算法

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择

贪心算法一般按如下步骤进行：
1、建立数学模型来描述问题
2、把求解的问题分成若干个子问题
3、对每个子问题求解，得到子问题的局部最优解
4、把子问题的解局部最优解合成

举个简单的贪心算法：柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。每位顾客只买一杯柠檬水，然后向你付
5 美元或10 美元或 20 美元。
你必须给每个顾客正确找零，注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false

如客户给了20，可以找10+5，或5+5+5，解答时优先给10+5就算是贪心，因为张数最少

var lemonadeChange = function (bills) {
  let fiveNum = 0; //5元0张
  let tenNum = 0; //10元0张
  for (let i = 0; i < bills.length; i++) {
    let bill = bills[i]; //第i个客户给了张多少元的钱
    if (bill === 5) {
      fiveNum += 1;
    } else if (bill === 10) {
      //客户给10元+，有5元找-，没发找则false
      if (fiveNum > 0) {
        fiveNum -= 1;
        tenNum += 1;
      } else {
        return false;
      }
    } else {
      //客户给20的情况
      if (tenNum >= 1 && fiveNum >= 1) {
        //优先找10+5
        fiveNum -= 1;
        tenNum -= 1;
      } else if (fiveNum >= 3) {
        //其次找5+5+5
        fiveNum -= 3;
      } else {
        return false;
      }
    }
  }
  return true;
};