*算法训练（leetcode）第二十五天 | 134. 加油站、135. 分发糖果、860. 柠檬水找零、406. 根据身高重建队列

134. 加油站

leetcode题目地址

记录全局剩余油量和当前剩余油量，当前剩余小于0时，其实位置是当前位置的后一个位置。若全局剩余油量为负，则说明整体油量不足以走完全程。

小trick：可以加速c++程序运行。

// c++
cin.tie(nullptr) -> sync_with_stdio(false);

cin.tie(nullptr)：避免调用cin时自动刷新cout。
sync_with_stdio(false)：关闭 C++ 标准流与 C 标准流同步（例如cin和scanf同步）。

下面另一种写法：

// c++
std::ios::sync_with_stdio(false); // 关闭 C 和 C++ 流的同步
std::cin.tie(nullptr); // 解开 cin 和 cout 的绑定

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// c++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        cin.tie(nullptr) -> sync_with_stdio(false);
        int start=0, rest=0, all=0;
        for(int i=0; i<gas.size(); i++){
            rest += gas[i]-cost[i];
            all += gas[i]-cost[i]; 
            if(rest<0) {
                rest=0;
                start = i+1;
                
            }
        }
        if(all<0) return -1;
        return start;

    }
};

135. 分发糖果

leetcode题目地址

先初始化糖果列表均为1，因为每个人至少发一个。先从前向后检查，若后一个大于前一个，则后一个糖果等于前一个糖果+1。
再从后向前检查，若后一个小于前一个，将前一个糖果赋值为max(当前糖果，后一个糖果+1)。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// c++
class Solution {
public:
    int candy(vector<int>& ratings) {
        cin.tie(nullptr) -> sync_with_stdio(false);
        int all=0;
        vector<int> candies(ratings.size(), 1);

        for(int i=1; i<ratings.size(); i++){
            if(ratings[i-1]<ratings[i]){
                candies[i] = candies[i-1]+1;
            }
        }
        for(int i=ratings.size()-2; i>=0; i--){
            if(ratings[i+1]<ratings[i]){
                candies[i] = max(candies[i+1]+1, candies[i]);
            }
        }
        for(int i=0; i<candies.size(); i++){
            all += candies[i];
        }
        return all;
    }
};

860. 柠檬水找零

leetcode题目地址

记录5元和10元的个数，当出现找不开就返回false。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

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

406. 根据身高重建队列

leetcode题目地址

思路来源

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
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>> result;

        for(int i=0; i<people.size(); i++){
            int pos = people[i][1];
            result.insert(result.begin()+pos, people[i]);
        }

        return result;
    }
};