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

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

题目链接：1005.K次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

文章讲解/视频讲解：https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

思路

采用贪心的方法。为了达到题目的目的，我们需要在每次取反时选择数组中的最小值，这样得到的数组和便是可能的最大和。

如何在每次获得数组中的最小值呢？可以采用优先级队列，小顶堆。每次从堆顶取出最小值并取反后，再加入这个优先级队列之中。

C++实现

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> Q;
        int result = 0;
        for(auto& num : nums){
            Q.push(num);
            result += num;
        }

        for(int i = 0;i<k;i++){
            int cur = Q.top();
            Q.pop();
            result -= 2 * cur;
            Q.push(-cur);
        }
        return result;
    }
};

134. 加油站

题目链接：134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

文章讲解/视频讲解：https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

思路

将gas数组减去cost数组，便得到了车辆在对应车站汽油的净增值。

如果净增值加起来小于零，说明车辆不可能环绕一圈。

那么怎么判断从一个加油站i为起点，能够环绕一圈呢？

以示例1，gas = [1, 2, 3, 4, 5]，cost = [3, 4, 5, 1, 2]为例，净增值数组gain = [-2, -2, -2, 3, 3]，如果从下标0开始，净增数组从下标0开始的累加结果为：accumulates = [-2, -4, -6, -3, 0]，只有最后一个下标非负，其余累加结果都是负的，说明从下标0开始不成立。

如果从下标1开始，净增数组的累加结果为：accumulates = [0, -2, -4, -1, 2]，有两个下标为非负，依然不成立。

如果从下标3开始，净增数组的累加结果为：accumulates = [4, 2, 0, 3, 6]，所有下标都非负，因此成立。

我们希望能够找到一个累加结果，所有下标都非负。注意到，累加数组随着下标i的移动，每一位都是同时减去-gain[i - 1]这个数值，而累加数组中的最小值始终在下标2这个位置，是不变的。因此我们可以遍历滑动累加结果，找到一个使下标2这个位置的值非负的起始位置。

C++实现

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

        int minAccumulate = numeric_limits<int>::max();
        int curAccumulate = 0;
        for(int i = 0;i<gains.size();i++){
            curAccumulate += gains[i];
            minAccumulate = min(minAccumulate, curAccumulate);
        }
        if(minAccumulate >= 0) return 0; // 当前下标0满足条件
        
        for(int i = 1;i<=gains.size();i++){
            minAccumulate -= gains[i - 1];
            if(minAccumulate >= 0) return i;
        }
        return -1;
    }
};

135. 分发糖果

题目链接：135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

文章讲解/视频讲解：https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

思路

寻找ratings构成的折线图的上坡和下坡。

处在上坡中的所有孩子，他们分到的糖果都是其左边孩子糖果+1。处在下坡中的所有孩子，他们分到的糖果都是其右边孩子糖果+1。

坡峰是上下坡的交点，这个位置的孩子分到的糖果是其左右孩子糖果最大值+1。

另外，如果几个孩子的ratings连续相同，处在中间的孩子们分到的糖果也为1个。

具体细节可以参考代码，有点复杂。

看了卡哥的教程，可以前向遍历和后向遍历两层循环，不用管ratings连续相同的情况。

C++实现

// 自己的思路
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);
        int index = 0;
        while(index < ratings.size()){
            if(index + 1 < ratings.size() && ratings[index + 1] > ratings[index]){
                candies[index] = 1;
                while(index + 1 < ratings.size() && ratings[index + 1] > ratings[index]){
                    candies[index + 1] = candies[index] + 1;
                    index++;
                }
            }
            else if(index + 1 < ratings.size() && ratings[index + 1] < ratings[index]){
                int start = index;
                int pre = candies[start];
                while(index + 1 < ratings.size() && ratings[index + 1] < ratings[index]){
                    index++;
                }
                candies[index] = 1;
                for(int i = index - 1;i>=start;i--){
                    candies[i] = candies[i + 1] + 1;
                }
                candies[start] = max(candies[start], pre);
            }
            else if(index + 1 < ratings.size() && ratings[index + 1] == ratings[index]){
                while(index + 1 < ratings.size() && ratings[index + 1] == ratings[index]){
                    candies[index + 1] = 1;
                    index++;
                }
            }
            else{
                // index + 1 == ratings.size()
                index++;
            }
        }

        int totalCandies = 0;
        for(auto& candy: candies) totalCandies += candy;
        return totalCandies;
    }
};

// 前向后向两遍遍历
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);
        for(int i = 1;i<ratings.size();i++){
            if(ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        }
        for(int i = ratings.size() - 2;i>=0;i--){
            if(ratings[i] > ratings[i + 1]){
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }
        int result = 0;
        for(auto candy: candies) result += candy;
        return result;
    }
};