【力扣刷题 | 第十九天】

旧城等待， 2024-03-17 20:08 16阅读 0赞

![e387215a0e0d4caea6e6f03a97cb237d.jpeg][]

**目录**

前言：

135. 分发糖果 - 力扣（LeetCode）

860. 柠檬水找零 - 力扣（LeetCode）

总结：

--------------------

## 前言： ##

今天着重刷贪心算法的题目

## [135. 分发糖果 - 力扣（LeetCode）][135. _ - _LeetCode] ##

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

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

每个孩子至少分配到 1 个糖果。  
相邻两个孩子评分更高的孩子会获得更多的糖果。  
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

![1d8e056ba5084a08bf8814d510417f08.png][]

这道题的难点在于如何确定当前孩子所得的糖果值一定始终比两边孩子所得到的糖果多，很多人会想到对每一个孩子的左右同时进行比较，写成了这种（也有的只是把）：

for(int i=0;i<ratings.size()-1;i++)
           {
               if(ratings[i]<ratings[i+1])
               {
                   nums[i+1]=1+nums[i];
               }
               else if(ratings[i]>ratings[i+1] )
               {
                   nums[i]=nums[i+1]+1;
               }
           }

但实际上这种做法是有漏洞的，因为实际上在比较的时候，每一个孩子手里的糖果数量都会发生变化，而相应的如果要多的话，也就要进行动态调整，如果按照上面的写法，就容易出现这种，也就是3一开始比2大，因此3拿两颗糖果

初始：![fc671dfe2474486ba54a485b8289a627.png][]

最终：![a081197b1f3644bf96061f67a703a844.png][]

解释：最开始都是1，3比2大，因此3的糖果加一变为2，再向后2比1大，加一，因此2的糖果书加一变为2，我们发现忽略了两个都加之后，3明明比2大，但是我们因为是一直向后遍历，并没有考虑到实时变化，因此才会出现这种情况

因此不能使用这种，很多人又会想到把这两个if语句分开，但实质上动态调整不是拆分if的问题，而是遍历顺序的问题，在比较左右孩子的时候，我们在比较完一侧孩子之后，在比较另一次的时候，应该从后往前遍历，这样才可以实时掌握变化。

因此这道题最好的方法就是拆开比较，我们先保证每一个孩子一定比他左边的孩子拿到的糖果多，再保证每一个孩子一定比他右边的孩子拿到的糖果多，这个来进行解题

其实这道题的核心并**不在于怎么分糖果**，因为这很好想清楚：**我们如果想尽可能少的分糖果，就只多一颗**

class Solution {
    public:
        int candy(vector<int>& ratings) {
            vector<int> nums(ratings.size(),1);
           
            // 一定比左边的孩子拿到的多
            for(int i=1;i<ratings.size();i++)
            {
                if(ratings[i]>ratings[i-1] )
                {
                    nums[i]=1+nums[i-1];
                }
            }
    
            // 一定比右边的孩子拿到的多
             for (int i = ratings.size() - 2; i >= 0; i--) 
             {
                if (ratings[i] > ratings[i + 1] )
                {
                   nums[i] = max(nums[i], nums[i + 1] + 1);
                }
            }
            int sum = 0;
            for(int i=0;i<nums.size();i++)
            {
                sum = sum + nums[i];
            }
            return sum;
        }
    };

## [860. 柠檬水找零 - 力扣（LeetCode）][860. _ - _LeetCode] ##

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

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

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

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

![06a0a73d8a0c40ec88a5c5d6a8f085ba.png][]

思路很清晰的一道题，时刻记录当前手里的5 和 10钞票面额就可以了，每一次找零前进行判断是否够找零，不用纪录20的张数，因为这个题最大找零是15。唯一贪心 的地方是：因为 5 元既可以找10元，也可以找20，因此在找20的时候，我们优先消耗10，这样才可以尽可能多的找零。

class Solution {
    public:
        bool lemonadeChange(vector<int>& bills) {
            int five = 0, ten = 0;
            for (int bill : bills) {
              
                if (bill == 5) 
                {
                    five++;
                }
              
                if (bill == 10) {
                    if (five <= 0)
                    {
                        return false;
                    } 
                    ten++;
                    five--;
                }
                
                if (bill == 20) {
                  
                    if (five > 0 && ten > 0)
                    {
                        five--;
                        ten--;
                       
                    } else if (five >= 3) {
                        five -= 3;
                   
                    } else return false;
                }
            }
            return true;
        }
    };

## 总结： ##

两道题都是贪心算法题目，尤其是柠檬水题目，我一开始还想着用数组来存储当前拥有的零钱，大大增加了题的复杂程度，其实可以直接用变量来记录的，下次做题前一定要思维足够开阔！

如果我的内容对你有帮助，请**点赞，评论，收藏**。创作不易，大家的支持就是我坚持下去的动力！

![69e9169c980f43e0aad31ff9ada88a9c.png][]

[e387215a0e0d4caea6e6f03a97cb237d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/44be9f0b760145efa7aed3cb1b080f8c.png
[135. _ - _LeetCode]: https://leetcode.cn/problems/candy/
[1d8e056ba5084a08bf8814d510417f08.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f45cb0fcff524f37b14266a83b77404d.png
[fc671dfe2474486ba54a485b8289a627.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2f1b750ba306457887d0ae5c8a148187.png
[a081197b1f3644bf96061f67a703a844.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f02171d6f689488a9d94b66a2d09a36c.png
[860. _ - _LeetCode]: https://leetcode.cn/problems/lemonade-change/
[06a0a73d8a0c40ec88a5c5d6a8f085ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/265f3176054243ab968e852710f091c0.png
[69e9169c980f43e0aad31ff9ada88a9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/dcfe4e47117b40f894edf27a09b819bd.png