*算法训练（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;}
};