【代码随想录|贪心算法03】

134.加油站

题目链接： 134. 加油站 - 力扣（LeetCode）

这道题是问我从哪个点开始遍历我的加油油量减去消耗掉的油量都为正，我感觉死扣根本想不出来一点。

这里的思路是保存每个站的的加油量减去消耗量(cursum)，他为正我肯定就能进行遍历，然后如果一个不小心，你油不够了(cursum<0)，那这个点前面的点肯定都不够这个点消耗的了，因为题目说存在解结果是唯一的，那我只要从后面的第一个油是正数的点开始遍历就足够了（按道理我第二个油是正数的点可能也可以，但是题目说只有一个解所以取第一个）

//错误代码
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalsum=0,cursum=0,start=0;
        for(int i=0;i<gas.size();i++){
            totalsum=gas[i]-cost[i];
            cursum=gas[i]-cost[i];
            if(cursum<0){
                start=i+1;
                break;//不能直接退出，后面可能还有负数点
            }
        }
        if(totalsum<0)return -1;
        return start;

    }
};

在做的时候，发现我这个不对，我最开始想的是我要第一个正数点那，取到了我退出了不就好了，然后报错的一组数据是

gas:[1, 2, 3, 4, 5]

cost:[3, 4, 5, 1, 2]

那么我每个站点需要消耗的量

rest:[-2,-2,-2,3,3]

这里如果cursum取到负数就退出的话我结果就会是1了，后来想想 我确实是要从负数的下一个作为起点，但是当我遇到负数的时候还要进行统计，因为有可能我负数的后面还是负数，所以不能直接退出。遇到负数的时候把cursum置零老老实实继续遍历吧~

//正确代码
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalsum = 0, cursum = 0, start = 0;
        for (int i = 0; i < gas.size(); i++) {
            cursum += gas[i] - cost[i];
            totalsum += gas[i] - cost[i];//统计整个进油出油量，放这里偷懒少写一个循环
            if (cursum < 0) {
                start = i + 1;
                cursum = 0;
            }
        }
        if (totalsum < 0)
            return -1;//每个站点需要消耗的量加起来都是负数了，肯定找不到
        else
            return start;
    }
};

135.分发糖果

题目链接135. 分发糖果 - 力扣（LeetCode）

这道题如果两边一起比较的话写代码会很混乱，这里思路是先从前往后进行遍历，右边孩子评分和左边孩子评分进行比较，给糖果，然后从后往前进行遍历，左边孩子评分和右边孩子评分进行比较，更新最大糖果值。

局部最优：满足从前往后遍历和从后往前遍历的孩子都拿到相应的糖果。

全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int result = 0;
        vector<int> candy(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }//右边孩子和左边孩子进行比较，所以从第二个开始
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = max(candy[i + 1] + 1, candy[i]);
            }//左边孩子和右边孩子进行比较，所以从倒数第二个开始
        }
        for (int i = 0; i < ratings.size(); i++) {
            result += candy[i];//统计总共的糖果数
        }
        return result;
    }
};

860.柠檬水找零

题目链接：860. 柠檬水找零 - 力扣（LeetCode）

这里有三种情况

一、收到的钱是5

那就美滋滋，也不用补

二、收到的钱是10

得看看我现在还有没有5块哦，没有就只能return false了

三、收到的钱是20

优先补10块+5块的，其次再补3个5块。 因为我的5块可以补10块和20，但是10块只能补20，所以优先把10块的给用了。

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

406.根据身高重建队列

题目链接：406. 根据身高重建队列 - 力扣（LeetCode）

因为这道题要从两个维度来考虑，所以要分别从两边开始贪

如果先从前面有k个人的k开始贪的话身高确定不下来，k也确定不下来，因为前面按照k从小到大排列 k根本就不能代表前面有多少人，比如说[1,0][1,0][1,0][1,1]，你的k等于1，但是前面有3个人

所以要从身高(h)开始排，

排之前：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

排之后：people=[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

身高(h)确定下来之后再确定k（前面有k个人），就挨着一个个进行比较，身高低前面排的人少的就给他插到前面去，因为这样也不会影响后面的结点

过程：

• 插入[7,0]：[[7,0]]
• 插入[7,1]：[[7,0],[7,1]]
• 插入[6,1]：[[7,0],[6,1],[7,1]]
• 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
• 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
• 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if (a[0] == b[0])
            return a[1] < b[1];
        return a[0] > b[0];//身高从大到小排，身高相同k大的排后面
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);//把整个顶点数据插到相应位置
        }
        return que;
    }
};