Day34｜贪心算法part03：1005.K次取反后最大化的数组和、134. 加油站、135.分发糖果

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

按照“绝对值”从大到小排序，如果数字小于0将其翻转，最后检查k有没有用完，没用完就反复翻转绝对值最小的数。

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum = 0;
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] < 0 && k > 0){
                nums[i] = -nums[i];
                k--;
            }
        }
        if(k % 2 == 1){
            nums[n - 1] = -nums[n - 1];
        }
        return Arrays.stream(nums).sum();
    }
}

IntStream.of(nums): 这一步将nums数组转换为一个IntStream流。

.boxed(): 这一步将IntStream流转换为Stream流。这是因为IntStream流没有sorted()方法可以接受自定义的比较器，而Stream流可以。

.sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)): 这一步使用自定义的比较器对流中的元素进行排序。比较器的作用是比较两个元素的绝对值大小，并按照从大到小的顺序排序。

.mapToInt(Integer::intValue): 这一步将Stream流转换回IntStream流。这是因为我们最终需要的是一个int数组，而不是Integer数组。

.toArray(): 这一步将IntStream流转换为int数组。

• Arrays.stream(nums).sum();计算数组的和。

134. 加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int n = gas.length;
        int index = 0;
        for (int i = 0; i < n; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if(curSum < 0){
                curSum = 0;
                index = (i + 1) % gas.length;
            }
        }
        if(totalSum < 0){
            return -1;
        }
        return index;
    }
}

• 贪心思想：

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置

• 局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置

135. 分发糖果

class Solution {
    /**
     分两个阶段
     1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
     2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
     */
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candyVec = new int[len];
        candyVec[0] = 1;
        for (int i = 1; i < len; i++) {
            candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
        }

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

        int ans = 0;
        for (int num : candyVec) {
            ans += num;
        }
        return ans;
    }
}

两次贪心，一次从左往右（从1开始），一次从右往左（从len-2开始）