文章参考来源代码随想录
134. 加油站
方法一分类讨论：
情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从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;
if (curSum < min) {
min = curSum;
}
}
if (curSum < 0) return -1; // 情况1
if (min >= 0) return 0; // 情况2
// 情况3
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开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。（反例可以通过简单的数学推断证明不成立）
局部最优：找到当前和为负数的位置（没油了）清空当前和，找到之后当前和大于零的位置。
全局最优：找到唯一起始位置
这里我们通过每次当前和小于零时，更新目标位置（后一位）并清空当前和直至当前和大于零，以此来找到第一次出现当前和大于零的位置。
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<gas.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. 分发糖果
如果两边一起考虑一定会顾此失彼。
所以这里采用两次遍历
从前往后：找出右大于左的
局部最优1：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
从后往前：找出左大于右的
疑惑点：为什么不能从前向后遍历呢？因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果，所以 要从后向前遍历
如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。
因此，局部最优2：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
class Solution {
public:
int candy(vector<int>& ratings) {
int sum=0;
vector<int>candy(ratings.size(),1);
for(int i=0;i<ratings.size()-1;i++){
if(ratings[i]<ratings[i+1])candy[i+1]=candy[i]+1;
}
for(int i=ratings.size()-1;i>0;i--){
if(ratings[i]<ratings[i-1])candy[i-1]=max(candy[i-1],candy[i]+1);
}
for(int k:candy)sum+=k;
return sum;
}
};860.柠檬水找零
5,10,20
付5直接不用找，付10找5，付20找10+5或者5+5+5
局部最优：优先消耗10（5更通用）去完成本次找零
全局最优：完成全部账单的找零
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five=0;
int ten=0;
int twenty=0;
for(int k:bills){
if(k==5)five++;
if(k==10){
if(five<=0)return false;
ten++;
five--;
}
if(k==20){
if(ten>0&&five>0){
ten--;
five--;
}
else if(five>=3)five-=3;
else return false;
}
}
return true;
}
};406.根据身高重建队列
本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列
如果两个维度一起考虑一定会顾此失彼。
由题意我们这里先确定一个维度排序——h
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性
所以这里先按身高排序，身高相同再按k排序（这里可以写一个cmp）
之后取每个元素的k为位置一个一个插进去即可
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;
}
};但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。
所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是O(n^2)了，甚至可能拷贝好几次，就不止O(n^2)了。
这里给出改为链表的代码
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);
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();
// 这行代码的作用是声明一个迭代器 it，它的类型是 std::list<vector<int>>::iterator，
//这个迭代器用于遍历 que 这个 std::list 容器中的 vector<int> 类型的元素。
while (position--) { // 寻找在插入位置
it++;
}
que.insert(it, people[i]);
}
return vector<vector<int>>(que.begin(), que.end());
}
};