【代码随想录day29】【C++复健】134. 加油站；135. 分发糖果；860.柠檬水找零；406. 根据身高重建队列
感觉贪心的题真的很考验一个人的智商，而我，碰巧没有。
134. 加油站
偷看了解析思路，但依然因为一个低级失误导致被卡了很久... 并且写出来的代码也非常的麻烦，主要体现在我每到一个新节点，就必须求证似的让iter走完一整圈才算结束，但卡哥的方法一个for循环就结束了。
卡哥的思路也相当的清晰：
简单来说就是当你一圈下来：
1 如果和小于0，那么说明无论如何无解，也不用往后再看了。
2 如果和大于0，那么一圈之内必有解，假设从i开始不行，跳i+1，i+1假设后半段没问题，那再往后我也不管了，因为[0, i]如果没有的话，一定是在[i+1, n]，又因为解唯一，假设某个位置能走到最后，后面的也不用看了。
我的这个代码就不用看了，写的太复杂了。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
vector<int> plmi;
for(int i=0; i<gas.size(); i++){
plmi.push_back(gas[i]-cost[i]);
}
int sum = 0;
for(int i=0; i<gas.size(); i++){
sum += plmi[i];
}
if(sum < 0){
return -1;
}
int count = 0;
int start = 0;
int iter = 0;
int gas_remain = 0;
while(count < gas.size()+1){
gas_remain += plmi[iter];
if(gas_remain < 0){
count = 0;
start = iter+1;
gas_remain = 0;
if(start >= gas.size()){
return -1;
}
}
else{
count++;
}
iter += 1;
if(iter >= gas.size()){
iter = 0;
}
}
return start;
}
};135. 分发糖果
没有太多思路，就去看了解析，只能说看了解析之后接受的也有点勉强，主要感觉思维里面有几个比较重大的坎：
坎1：想到前后分着处理
这一步就足够难倒大多数英雄好汉了，感觉初见就是得被杀啊。所以我也是直接偷看了解析。
坎2：前后遍历完了，这两个数组怎么处理得到答案？
偷看了解析发现前后分着处理后，我直接把代码写出来了，但拿着这俩数组又不知道怎么办了。最后看卡哥的解析视频才终于把取max的合理性给看懂。简单来说就是左到右只满足右大于左时糖分的多，右到左只满足左大于右时糖分的多，两个取最大就是两边都满足了。
简单来说，就是大小关系在左到右和右到左的时候是错开的，不会出现两个数左到右遍历的时候要求右大于左，右到左遍历又要求左大于右，这种情况是不存在的。
class Solution {
public:
int candy(vector<int>& ratings) {
int can = 1;
vector<int> left(ratings.size());
for(int i=0; i< ratings.size(); i++){
if(i >0 && ratings[i]>ratings[i-1]){
can++;
left[i] = can;
}
else{
can = 1;
left[i] = 1;
}
}
int can2 = 0;
vector<int> right(ratings.size());
for(int j=ratings.size()-1; j>=0 ; j--){
if(j <ratings.size()-1 && ratings[j]>ratings[j+1]){
can++;
right[j] = can;
}
else{
can = 1;
right[j] = can;
}
}
int sum = 0;
for(int i = 0; i<ratings.size(); i++){
sum += max(left[i], right[i]);
}
return sum;
}
};860.柠檬水找零
思路和卡哥一样，也一遍做出来了，没什么太多好说的。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int num5 = 0;
int num10 = 0;
for(int i=0; i<bills.size(); i++){
if(bills[i] == 5){
num5++;
}
else if(bills[i] == 10){
num10++;
num5--;
if(num5 < 0){
return false;
}
}
else if(bills[i] == 20){
if(num10 >0){
num10--;
num5--;
}
else{
num5 -= 3;
}
if(num5 < 0){
return false;
}
}
else{
return false;
}
}
return true;
}
};406.根据身高重建队列
关键问题1：分治先治哪边？
粗浅一看毫无思路，哪怕有了卡哥“类似分糖果，要先处理一边”的提示，还是想不出来，想到肯定是先处理h和k的其中一个，但是感觉给h排序没意义，给k排序更是毫无用处，就卡在这里了，感觉是自己想错了，就去偷看了解析。
然后卡哥表示：
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];
}没错，我确实分治了，但也没完全分，我在排h的时候顺便给k也排了，没想到吧！
这样做的好处是极其明显的，因为如果不顺便排k的话，就会发现，你先插入的位置在后面还会发生变动，那就白排了。举个例子：[7,0], [7,1], [5,2], [5,0]，假设我们先把前三个排好，后来发现[5,0]要排在[7,0]以前，那前面本来已经排好的[5,2]的位置就不对了，全部木大。
而如果顺便给k也排过的话，就可以保证[5,0]一定会在[5,2]之前出现，这样就能保证之前的积累，并非全部木大，未来的道路也会不断延伸...
关键问题2：要新建一个Vector！
冥思苦想了半天如果我要把原本在第i号位的元素挪到people[i][1]去的话应该怎么对数组进行操作，已经想到了说如果i比people[i][1]小的话，就从i+1开始，到people[i][1]为止，每个元素都往左挪动一格，然后再把i号位原本的元素挪到people[i][1]去，但后来一想，这还是个二维vector，赋值也是个超级大麻烦，索性直接去看解析了。一看恍然大悟，直接新建一个vector不就好了吗！
可能是受了之前那些原地操作的代码题的影响了，但真没必要，一切以俺代码写得舒服为最优先准则。
关键问题3：用vector还是用链表？
关于给vector补点插入值时会发生全量拷贝的事情也是有所耳闻的，也知道链表会更好，但奈何...
链表的定义都忘记了你敢信！用的是什么关键词来着？
好吧，原来就是list，写成list<vector<int>>，并且为了遍历我们还需要再定义一个迭代器，迭代器内置了++操作，每次position--，it就++，直到potision减到0。
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();
while (position--) { // 寻找在插入位置
it++;
}
que.insert(it, people[i]);
}只能说全是细节，我估计是写不出来的，更何况最后还有一个转换：
return vector<vector<int>>(que.begin(), que.end());怎么说呢，都是一看就懂，一写就废，根本不知道要传什么参，怎么写。