代码随想录算法训练营第三十四天 | 1005.K次取反后最大化的数组和，134. 加油站， 135. 分发糖果

本文主要是介绍代码随想录算法训练营第三十四天 | 1005.K次取反后最大化的数组和，134. 加油站， 135. 分发糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
贪心，每次选择最小的数来取反
用了一个优先级队列来做处理，维护一个顺序的数组

class Solution {
public:typedef struct comp{bool operator()(const int & a,const int & b){return a > b;}}comp;int largestSumAfterKNegations(vector<int>& nums, int k) {int res = 0;priority_queue<int,vector<int>,comp> pq;for(auto & num : nums){pq.push(num);}for(int i = 0;i< k;i++){int minNum = pq.top();pq.pop();pq.push(minNum * -1);}for(int i = 0;i< nums.size();i++){int num = pq.top();pq.pop();res += num;}return res;}
};

在这里插入图片描述

这道题是一个贪心问题，从0下标起点出发，一直加油，耗油，前进，一直到某个位置耗油大于已有的油量时再也无法前进，那么也就是说，从起点到当前终止的位置，都是不能作为起点使用的：
很好理解吧，在每个节点其实都有加油 - 耗油 = 净加油量，某个节点无法寸进以后，也就是说明，在起点出发的这个区间内，净油量无法满足消耗，需要在其它区间出发，用其他位置的净油量来把这里的缺口补上，由于我们是从0开始的，那么这一整段都不要了，下一个区间紧贴当前终止位置，继续查看

如果发现整个区间都没有起点（净油量无法满足消耗），就返回-1

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

在这里插入图片描述
这道题需要维护数组元素的左右关系，需要注意，一般的做法是把左右关系分开来维护，不要同时维护，要不会很乱

本题是从前往后遍历，先维护右孩子大于左孩子的+1
那么，这个遍历次序下可以确保前面填定的值不会受到后面的影响

然后是在右孩子大于左孩子的+1的基础上，从后往前遍历，维护左孩子大于右孩子的+1

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