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

1005.K次取反后最大化的数组和
本题简单一些，估计大家不用想着贪心 ，用自己直觉也会有思路。
https://programmercarl.com/1005.K次取反后最大化的数组和.html

自己写的时间复杂度太高，看答案优化
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function(nums, k) {
    while(k>0){
        let min = Infinity;
        let index = 0;
        for (let i=0;i<nums.length;i++) {
            if (min>nums[i]) {
                min = nums[i];
                index = i;
            }
        }
        nums[index] = -nums[index];
        k--;
    }
    let total = nums.reduce((total, cur)=>{
        return total += cur;
    }, 0)
    return total;
};

134. 加油站
     本题有点难度，不太好想，推荐大家熟悉一下方法二
     https://programmercarl.com/0134.加油站.html

基本上想不出
/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    let total = 0;
    let curSum = 0;
    let start = 0;
    for (let i=0;i<gas.length;i++) {
        curSum += gas[i] - cost[i];
        total += gas[i] - cost[i];
        if (curSum < 0) {
            start = i + 1;
            curSum = 0;
        }
    }
    if (total<0) return -1;
    return start;
};

135. 分发糖果
     本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路
     https://programmercarl.com/0135.分发糖果.html

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let len = ratings.length;
    let candy = new Array(len).fill(1);

    for (let i=1;i<len;i++) {
        if (ratings[i]>ratings[i-1]) {
            candy[i] = candy[i-1]+1;
        }
    }

    for (let i=len-2;i>=0;i--) {
        if (ratings[i]>ratings[i+1]) {
            candy[i] = Math.max(candy[i+1]+1, candy[i]);
        }
    }

    let total = 0;
    for (let i=0;i<len;i++) {
        total += candy[i];
    }
    return total;
};