134. 加油站

题目链接：https://leetcode.cn/problems/gas-station/
题目难度：中等
文章讲解：https://programmercarl.com/0134.加油站.html
视频讲解：https://www.bilibili.com/video/BV1jA411r7WX
题目状态：没有思路，学习题解

思路一：全局最优解

首先将所有路径的加油量和耗油量加一起，看是否大于0，若小于0，表示整体的加油量小于耗油量，不可能跑完全程，直接返回-1；若大于0，看其到每一站存储的油量最小值是否大于等于0，若是，则表示其在每一站都是可以跑完的，直接返回0（表示从0开始出发可以完成全程）；若并不是这样的，则反向加出发点，看其什么时候的最小值不会为负数，此时就是出发点的位置。

代码一：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int min = INT_MAX;
        for(int i = 0; i < gas.size(); ++i) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            min = std::min(min, curSum);
        }
        if(curSum < 0) return -1;
        if(min >= 0) return 0;

        for(int i = gas.size() - 1; i >= 0; --i) {
            int rest = gas[i] - cost[i];
            min += rest;
            if(min >= 0) return i;
        }
        return -1;
    }
};

思路二：贪心算法

局部最优，首先当所有路径的油差之和小于0，直接返回-1，其不可能跑完全程；再次，若从A点到B点的油差和小于0，要从B点的下一点重新记录，因为A到B之间无论从哪一点开始，都跑不完，最后返回合适的位置。

代码：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for(int i = 0; i < cost.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;
        return start;
    }
};

135. 分发糖果

题目链接：https://leetcode.cn/problems/candy/
题目难度：困难
文章讲解：https://programmercarl.com/0135.分发糖果.html
视频讲解：https://www.bilibili.com/video/BV1ev4y1r7wN
题目状态：好难，要长脑子了

思路：

首先创建一个数组，存储每个孩子手里的糖。

• 首先，每个孩子手里都要有一颗糖。
• 从左向右，判断右边孩子分数是否要大于左边孩子，若大于，就把右边孩子手里加一颗糖。
• 从右向左，判断左边孩子的分数是否大于右边孩子，若大于，则判断左边孩子手里的糖是否已经大于右边孩子了，若不大于，则将左边孩子手里的糖加到比右边孩子大。

代码：

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVal(ratings.size(), 1);
        for(int i = 1; i < ratings.size(); ++i) {
            if(ratings[i] > ratings[i - 1]) candyVal[i] = candyVal[i - 1] + 1;
        }
        for(int i = ratings.size() - 2; i >= 0; --i) {
            if(ratings[i] > ratings[i + 1]) candyVal[i] = max(candyVal[i], candyVal[i + 1] + 1);
        }
        int res = 0;
        for(auto &val : candyVal) res += val;
        return res;
    }
};

860. 柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/
题目难度：简单
文章讲解：https://programmercarl.com/0860.柠檬水找零.html
视频讲解：https://www.bilibili.com/video/BV12x4y1j7DD
题目状态：没绕过来，看完题解豁然开朗

思路：

维护五块钱和十块钱的个数five和ten

• 当给5元时，five++；
• 当给10元时，five--；
• 当给20元时，要么ten--和five--，要么five-3。

代码：

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

406. 根据身高重建队列

题目链接：https://leetcode.cn/problems/queue-reconstruction-by-height/
题目难度：中等
文章讲解：https://programmercarl.com/0406.根据身高重建队列.html
视频讲解：https://www.bilibili.com/video/BV1EA411675Y
题目状态：继续学习题解...

思路：

首先对整个数组进行排序，排序规则是比较身高，最高的排在前面，若身高相同，比较前方人数，人数低的排在前面。
之后开始插入返回数组，按照排序后的数组依次插入，插入的位置是自己的前方人数，下图更容易理解插入的过程。

代码实现：

class Solution {
public:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        if(a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    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;
    }
};

链表代码：（性能更好）

class Solution {
public:
    // 身高从大到小排（身高相同k小的站前面）
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort (people.begin(), people.end(), cmp);
        list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1]; // 插入到下标为position的位置
            std::list<vector<int>>::iterator it = que.begin();
            while (position--) { // 寻找在插入位置
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};

热门相关：我真不是暴发户   【戏说台湾】寿桃太子爷   功夫圣医   赠我深爱如长风   勇闯天涯