代码随想录算法训练营Day31| 134. 加油站 ， 135. 分发糖果 ，860.柠檬水找零 ， 406.根据身高重建队列

135. 分发糖果：代码随想录

这道题目的意思就是给你一个ratings数组，代表每一个孩子的分数，你现在要根据这些分数来分发糖果，你需要用到尽可能少的糖果，并满足以下的条件，首先每个小孩的最少的糖果的数量为一个，然后就是相邻的小孩得分高的应该得到更多的糖果，那么这道题目我们该如何来求解呢

就像代码随想录里说的，遇到这种的情况，我们一定不能两边都考虑，比如说，我既要看是不是比右边的分数高，又要看是不是比左边的分数高，这样往往会顾此失彼，所以我们可以先考虑一个维度，然后再去考虑另一个维度，这里我们需要注意的一点是，如果说你要比较该孩子和左边的孩子比较哪个的值比较大，那你一定是要从左向右来看，为什么呢，因为只有这样你才能达到一种累加的效果，因为你需要保证得分高的孩子的糖果数量更多，那如果你不是从左到右的话，你就无法利用前面比较的结果了，反之也是一样的，我们只需要先跟左边的比较一遍，再跟右边的比较一遍，最后在两边取一个最大值，就可以保证我当前的这个孩是满足上面的条件的，至于上面说的那个是从左向右，还是从右向左，可以自己举一个例子试一试，来看具体的代码的实现

class Solution {
public:int candy(vector<int>& ratings) {vector<int> nums;for (int i = 0; i < ratings.size(); i++) {nums.push_back(1);}for (int i = 1; i < nums.size(); i++) {if (ratings[i] > ratings[i - 1]) {nums[i] = nums[i - 1]+1;}}for (int i = nums.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 += nums[i];}return sum;}
};

这里就是首先一开始所有的元素都初始化为1，因为需要满足所有的小孩都要得到一个糖果的条件，然后就是只要比左边的或者右边的分数高就将糖果的数量给加1，等于是不需要加的，最后累加返回结果就可以了。

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

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];else return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {vector<vector<int>> queue;sort(people.begin(), people.end(), cmp);for (int i = 0; i < people.size(); i++) {int position = people[i][1];queue.insert(queue.begin() + position, people[i]);}return queue;}
};