经典题目

分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例1：

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例2：

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。证明如下。

假设有 mm 个孩子，胃口值分别是 g1 到 gm ，有 nn 块饼干，尺寸分别是 s1 到 sn , 满足 gi <= gi+1 和 sj <= sj+1 ,其中 1<=i<m , 1<=j<n

假设在对前 i-1 个孩子分配饼干之后，可以满足第 ii 个孩子的胃口的最小的饼干是第 j 块饼干，即 sj 是剩下的饼干中满足 gi<=sj 的最小值，最优解是将第 j 块饼干分配给第 i 个孩子。如果不这样分配，考虑如下两种情形：

如果 i<m 且 gi+1 <= sj 也成立，则如果将第 j 块饼干分配给第 i+1 个孩子，且还有剩余的饼干，则可以将第 j+1 孩子，且还有剩余的饼干，则可以将第 j+1 块饼干分配给第 i 个孩子，分配的结果不会让更多的孩子被满足；
如果 j<nj<n，则如果将第 j+1 块饼干分配给第 i 个孩子，当 gi+1 <= sj 时，可以将第 j 块饼干分配给第 i+1 个孩子，分配的结果不会让更多的孩子被满足；当 gi+1>sj 时，第 j 块饼干无法分配给任何孩子，因此剩下的可用的饼干少了一块，因此分配的结果不会让更多的孩子被满足，甚至可能因为少了一块可用的饼干而导致更少的孩子被满足。

基于上述分析，可以使用贪心的方法尽可能满足最多数量的孩子。

首先对数组 g 和 s 排序，然后从小到大遍历 g 中的每个元素，对于每个元素找到能满足该元素的 s 中的最小的元素。具体而言，令 i 是 g 的下标，j 是 s 的下标，初始时 i 和 j 都为 0，进行如下操作:

对于每个元素 g[i]，找到未被使用的最小的 jj 使得 g[i] <= s[j]，则 s[j] 可以满足 g[i]。由于 g 和 s 已经排好序，因此整个过程只需要对数组 g 和 s 各遍历一次。当两个数组之一遍历结束时，说明所有的孩子都被分配到了饼干，或者所有的饼干都已经被分配或被尝试分配（可能有些饼干无法分配给任何孩子），此时被分配到饼干的孩子数量即为可以满足的最多数量。

function distributionOfBscuits(g,s){
  g.sort((a,b)=>a-b);
  s.sort((a,b)=>a-b);
  const numOfChildren=g.length;
  const numOfCookies=s.length;
  let count=0;
  for(let i=0,j=0;i<numOfChildren&&j<numOfCookies;i++,j++){
    while(j<numOfCookies&&g[i]>s[j]){
      j++
    }
    if(j<numOfCookies){
      count++
    }
  }
  return count
}

// const g=[1,2,3];
// const s=[1,1];
// console.log(distributionOfBscuits(g,s));
const g=[1,2];
const s=[1,2,3];
console.log(distributionOfBscuits(g,s));

性能分析:

时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是数组 g 和 s 的长度。对两个数组排序的时间复杂度是 O(mlogm+nlogn)，遍历数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。

空间复杂度：O(logm+logn)，其中 m 和 n 分别是数组 g 和 s 的长度。空间复杂度主要是排序的额外空间开销。

找零钱问题

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例1:

输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的。
第 4 位顾客那里，我们收取一张 10 美元的***，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的***和一张 5 美元的。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例2：

输入：[5,5,10]
输出：true

示例3:

输入：[10,10]
输出：false

示例4:

输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的***。
对于接下来的 2 位顾客，我们收取一张 10 美元的***，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的***。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

由于顾客只可能给你三个面值的***，而且我们一开始没有任何***，因此我们拥有的***面值只可能是 55 美元，1010 美元和 2020 美元三种。基于此，我们可以进行如下的分类讨论。

5 美元，由于柠檬水的价格也为 5 美元，因此我们直接收下即可。
10 美元，我们需要找回 5 美元，如果没有 5 美元面值的***，则无法正确找零。
20 美元，我们需要找回 15 美元，此时有两种组合方式，一种是一张 10 美元和 5 美元的，一种是 3 张 5 美元的，如果两种组合方式都没有，则无法正确找零。当可以正确找零时，两种找零的方式中我们更倾向于第一种，即如果存在 5 美元和 10 美元，我们就按第一种方式找零，否则按第二种方式找零，因为需要使用 5 美元的找零场景会比需要使用 10 美元的找零场景多，我们需要尽可能保留 5 美元的。

基于此，我们维护两个变量 five 和 ten 表示当前手中拥有的 5 美元和 10 美元的张数，从前往后遍历数组分类讨论即可。

function change(bills){
  let five=0;
  let ten=0;
  for(const bill of bills){
    if(bill==5){
      five+=1;
    }else if(bill==10){
      if(five==0){
        return false
      }
      five-=1;
      ten+=1;
    }else{
      if(five>0&&ten>0){
        five-=1;
        ten-=1;
      }else if(five>=3){
        five-=3;
      }else{
        return false
      }
    }
  }
  return true
}

// const bills=[5,5,10];
// console.log(change(bills));

// const bills=[10,10];
// console.log(change(bills));

const bills=[5,5,10];
console.log(change(bills));

性能分析:

时间复杂度：O(N)，其中 N 是 bills 的长度。空间复杂度：O(1)。

总结:

这道问题之所以可以使用 贪心算法，完全是因为可以选择的面值只有 55 美元，1010 美元和 2020 美元。

分发饼干​

找零钱问题​

分发饼干

找零钱问题