134.加油站
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈
每个加油站的剩余量rest[i]为gas[i] - cost[i]
从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置
因为我们一直维护的是一个剩余量大于等于0的区间，如果突然小于0，那么可以思考，从start到i中任取一个位置j作为起点，则j到i位置所得到的剩余量和一定小于0, 累加和cursum [start,j] > 0,[start,i] <0,而i>j,所以[j,i]必定<0
所以我们需要重新选择起始点,start=i+1，cursum=0,重新开始计算剩余量
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.分发糖果
这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
局部最优：右边的孩子如果分数比左边大，就比左边多一颗
全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
但是单看右孩子还是无法满足题目条件，如
ratings:
[1,8,8,2,1]
光用右孩子会得到
[1,2,1,1,1]
这明显不满足条件，因为8比2大，2比1大，所以需要看左孩子
而且要从后向前遍历，因为r[i]和r[i-1]的比较要用上r[i]和r[i+1]的比较结果（糖果数)
如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。
局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candy(ratings.size(), 0);
candy[0] = 1;
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1])
candy[i] = candy[i - 1] + 1;
else
candy[i] = 1;
}
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candy[i] = max(candy[i], candy[i + 1] + 1);
}
}
int sum = 0;
for (int m : candy) {
sum += m;
}
return sum;
}
};
860.柠檬水找零
记录收到的钞票数，如果是5元就拿着，10元就判断是否有5元剩余，
20元就首先判断有没有1个10元和1个5元，没有就判断有没有3个5元
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
vector<int> pay(3, 0);
for (int i = 0; i < bills.size(); i++) {
if (bills[i] == 5) {
pay[0]++;
} else if (bills[i] == 10) {
if (pay[0] == 0)
return false;
pay[0]--;
pay[1]++;
} else {
if (pay[0] == 0)
return false;
else {
if (pay[1] != 0) {
pay[1]--;
pay[0]--;
} else {
if (pay[0] < 3)
return false;
else
pay[0] -= 3;
}
}
}
}
return true;
}
};
406.根据身高重建队列
遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。
那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！
首先按身高从高到低排序，然后从前往后遍历，如果有2个人比这个人高，则插入到下标为2的位置即可（前面两个人比他高）
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](vector<int> a, vector<int> b) {
if (a[0] == b[0])
return a[1] < b[1];
return a[0] > b[0];
});
list<vector<int>> res;
for (int i = 0; i < people.size(); i++) {
int pos = people[i][1];
auto it = res.begin();
while(pos){
it++;
pos--;
}
res.insert(it,people[i]);
}
return vector<vector<int>>(res.begin(),res.end());
}
};
