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;}
};