代码随想录 Day34 贪心算法 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果

1005.K次取反后最大化的数组和 

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        int i = 0;
        while(k > 0){
            nums[i] = 0 - nums[i];
            if( i+1 < nums.size() && nums[i] > nums[i+1] ){
                i++;
            }
//始终让指针保持在元素值最小的位置上
//对于i大小的判断需要放在前面，不然出现栈溢出
            k--;
        }
        for(int i = 0; i < nums.size(); i++){
            sum +=nums[i];
        }
        return sum;
    }
};

思路：

1. 感觉贪心算法依然是找到那个最核心的点突破，本题就是最核心就是每次变号都是找最小的那个元素，但是又不能每次变号以后再进行排序会超时。所以说归纳总结排序后的三种情况分别是负负负，负0正，和正正正情况。发现最小值一定是出现在刚刚变号的值或者是变号的下一个值中。

134. 加油站

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) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

思路：本题的思路是很有难度的，太难想了，先好好记住吧

就是如果说总油量是够用的情况下，那么那个起始点是会出现在累加油量为负值的下一个位置，如果出现多段负值的情况只能说明前面那每一段累加之后都是负值，只能说后来的一段是正值的话可以弥补，但是如果是总油量也是负值的话就是不行的。差不多理解一下就好，在总油量是正值的情况下是可以走完全程的。

135. 分发糖果  

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        // 统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};

思路：只能说简直了，没做过怎么相出来

首先是初始化所有的元素的数值大小都是1。

就是分为两种情况进行讨论，如果说右边的孩子比左边的孩子大的话就让右边的孩子糖果数相对于前面+1，如果持平就不变。

如果说左边的孩子比右边的孩子大的话，就让左边的孩子糖果数+1，如果是持平就不变，但是一定是要从右边开始遍历，因为需要从右边开始累加。

最后取两者数值中的最大值，这个时候两边的情况都可以满足。

比如说第i个元素它比i-1的元素要大，i-1比i元素要小，所以说在第一次遍历中使得右边糖果多，第二次遍历使得值是持平的，所以取最大值是可以满足两种情况。

题目稍微理解就好。