DAY38：贪心算法（六）分发糖果+柠檬水找零

135.分发糖果

• 本题涉及到一个思想，就是处理好一边再处理另一边，不要两边想着一起兼顾。也就是说递增递减都要处理的情况，需要遍历两遍。后面还会有题目用到这个思路。

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
1
2
3

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
1
2
3
4

提示：

• n == ratings.length
• 1 <= n <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

思路

本题大致思路如下图所示。注意，因为只给出了两个条件，没有说数值相等的情况，因此数值相等，又没有比左右评分高的情况，只需要基础的1就可以了。

本题，因为是相邻的孩子作比较，我们需要同时考虑两边的情况，也就是考虑左边的小孩和右边的小孩。

这种需要同时考虑两边的情况，例如同时需要比较左边小孩+右边小孩，一定要先确定一边，再确定另一边！也就是说需要把一边的情况全部确认完毕，再去确认另一边。两边一起比较一定会乱！

每个小孩既要和左边比较，又要和右边比较，此时首先确定一边，也就是右边小孩>左边小孩的情况。左边小孩>右边的情况，我们先不管。

第一种情况：右>左

右孩子>左孩子的情况：

这种情况，首先考虑极端情况，也就是一路都是右边>左边。这样的话，糖果的数量是从左到右累积，因此遍历也需要从左往右遍历。

//判断逻辑
if(rating[i]<rating[i+1]){
    candy[i+1]=candy[i]+1;
}
1
2
3
4

第二种情况：左>右（倒序遍历）

左孩子>右孩子的情况如图所示。注意，左>右这种情况需要从后往前遍历。

原因是，由于本题相邻孩子，评分更高会获得更多糖果，因此我们需要考虑极端情况，也就是一路上都是左>右的情况。

如果一路上都是左>右的情况，那么糖果的数目需要从后向前累积！也就是说，我们必须采用倒序遍历，才能接收到左孩子>右孩子的累积结果。

两种情况的结果合并，通过取最大值

第二种情况还有一个需要注意的问题，就是到了第二种情况的时候，candy[i]已经有第一种情况的数值了。此时，为了满足既要比较左边，又要比较右边，需要对两个方法得到的candy[i]取最大值。取最值的逻辑如下图：

绿色字体是第二个例子中，以右>左规则来遍历的结果。由此可见需要的操作是取max值。

//判断逻辑
for(int j=ratings.size()-1;j>0;j--){
    if(ratings[j]<ratings[j-1]){
        //此时candy[j]本身就有数值了，取一个最大值，从而同时满足两边的条件
        candy[j-1] = max(candy[j]+1,candy[j-1]);
    }
}
1
2
3
4
5
6
7

完整版

• 本题在左大于右的时候，必须采用倒序遍历，就是考虑了极端情况下，如果所有的孩子都是左大于右，评分数组降序排列，那么此时左边的孩子是累积了这个数组里所有的糖果情况！此时如果还是正序，那么将会导致左孩子没有累积到右孩子+1的结果（因为左孩子更大）
• 本题在左右两次遍历结果合并的时候，是取两次遍历结果里面的最大值。做一个单调递增/递减的例子就可以看出。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int>candy(ratings.size(),1);
        int sum=0;
        //先考虑右孩子大于左孩子
        for(int i=0;i<ratings.size()-1;i++){
            if(ratings[i]<ratings[i+1]){
                candy[i+1]=candy[i]+1;
            }
        }
        //再考虑左孩子大于右孩子
        for(int j=ratings.size()-1;j>=1;j--){
            if(ratings[j]<ratings[j-1]){
                //注意这里比较大的是candy[j-1]，需要和candy[j-1]本身数值进行取最值
                candy[j-1]=max(candy[j]+1,candy[j-1]);
            }
        }
        for(int i:candy){
            sum+=i;
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 时间复杂度: O(n)
• 空间复杂度: O(n)

总结

这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就一定会顾此失彼。评分数组既包含递增又包含递减的部分，必须经过两次遍历，一次遍历不能同时兼顾。

本题采用了两次贪心的策略：

• 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
• 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。另外，本题要注意极端情况考虑的思想，我们想到倒序遍历这个想法，主要就是考虑评分数组单调递减/单调递增的极端情况。

860.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

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

示例 2：

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

提示：

• 1 <= bills.length <= 10^5
• bills[i] 不是 5 就是 10 或是 20

思路

本题一开始手里是没有零钱的，只能靠收到顾客的钱。最开始感觉很复杂，但是本题的场景非常固定。

场景包括：

1.顾客支付了5，不用找零

2.顾客支付了10，能找零返回5，不能的话返回false

3.顾客支付了20，要么返回10和5，要么返回5和5和5，否则返回false

注意第三种情况，我们需要优先采用10和5这种策略，因为5更万能一些，5不仅可以对20找零，也可以对10找零，所以手头上要尽量留更多的5.

贪心的策略就是，遇到20的情况，优先用10进行找零。全局最优就是完成所有找零。

其他的策略都是固定的，场景也是固定的，直接写死即可。

完整版

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        //先定义三个变量，统计5，10，20的数量
        int five=0;
        int ten=0;
        int twenty=0;
        for(int i=0;i<bills.size();i++){
            if(bills[i]==5){
                five++;
                continue;
            }
            if(bills[i]==10){
                if(five==0) return false;
                else{
                    five--;
                    ten++;
                    continue;
                }
            }
            if(bills[i]=20){
                //优先用10+5的策略来找零
                if(ten>0&&five>0){
                    ten--;
                    five--;
                    twenty++;
                    continue;
                }
                //然后采用5+5+5的策略
                else if(five>=3){
                    five-=3;
                    twenty++;
                    continue;
                }
                else
                    return false;
            } 
        }
        //如果for结束了还没有return false，就说明可以遍历完所有顾客
        return true;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

• 时间复杂度: O(n)
• 空间复杂度: O(1)

总结

这道题目看起来比较复杂，但是实际上策略非常固定，因为顾客只有5 10 20三种情况，而且我们手里也没有其他面额的零钱，只能用5 10 20来进行找零。因此可以用if语句列出所有的情况，再配合贪心的策略，优先用10找零，留下5。

这道题目可以看出，遇到感觉没有思路的题目，可以静下心来把能遇到的所有情况分析一下，只要分析到具体情况了，一下子就豁然开朗了。

如果一直陷入想从整体上寻找找零方案，就会把自己陷进去，各种情况一交叉，只会越想越复杂。