代码随想录训练营第29天|控制变量

134. 加油站

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int cur=0, total=0, start=0;for(int i=0; i<gas.size(); i++){cur+=gas[i]-cost[i];total+=gas[i]-cost[i];if(cur<0){start=i+1;cur=0;}}if(start>=gas.size())return -1;if(total<0)return -1;return start;   }
};

cur用来累计新的起点下，所有油站的净利， 如果累计到i【首次】出现负值，则符合要求的起点一定在i后面。

反证法：

假设i之前存在一个符合题意的起点j（old_start<j<i），即在[j,i]的累计和为正，又因为[old_start,i]的累计和为负，则[old_start, j]区间内的累计和一定为负，换句话说，累计到小于i的j时，就已经出现了负值，这与i的【首次】性矛盾。

for循环结束后，start指向第一个在其之后累计和为正的位置（因为一旦遇到负就会更新start），此时该累计和表示后半段的盈利额，若全局盈利（total为正），则一定可以覆盖前半段的开支。

135. 分发糖果

class Solution {
public:int candy(vector<int>& ratings) {int n=ratings.size();vector<int> nums(n,1);for(int i=1; i<n; i++){if(ratings[i]>ratings[i-1])nums[i]=nums[i-1]+1;}for(int i=n-2; i>=0; i--){if(ratings[i]>ratings[i+1])nums[i]=max(nums[i],nums[i+1]+1);}return accumulate(nums.begin(),nums.end(),0);}
};

题目要求比相邻大，可以拆解为【比前面大】和【比后面大】两个子问题：

从前往后扫，假定前置元素已经符合要求，解决比前面大的问题；

然后，从后往前扫，假定后置元素已符合，解决比后面大的问题。

860. 柠檬水找零

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

贪心思想，遇到20的bill，优先使用10块找零，5块是最灵活的，省着用。

406. 根据身高重建队列

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];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(),people.end(),cmp);list<vector<int>> result;for(auto& p:people){int idx=p[1];auto it=result.begin();for(int i=0; i<idx; i++)it++;result.insert(it,p);}return vector<vector<int>>(result.begin(),result.end());}
};

需要频繁插入元素使用了list数据结构，根据身高降序排列后依次处理，考虑一个新的元素p（当前最小），根据要求的索引idx，直接插入指定位置，该操作的合理性：

1.list里元素都是大于p的，自然有idx之前的也大于p，即p这个元素是合理的。

2.考虑插入p后，p之前的元素，因为相对顺序较插入前没有变化，所以保持合理。

3.考虑插入p后，p之后的元素，虽然相较插入前有整体的后移，但是由于p是最小的，而idx记录的是大于元素的个数，因此p不会产生贡献，即idx不需要变化，因此也是合理的。