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

• 刷题https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
• 文章讲解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
• 视频讲解https://www.bilibili.com/video/BV138411G7LY/?vd_source=af4853e80f89e28094a5fe1e220d9062

• 题解：

class Solution {
    //需要先按照绝对值大小排序
    public int largestSumAfterKNegations(int[] nums, int k) {
        //将一个int数组转换为IntStream，然后将其装箱为Integer对象，
        //按照绝对值的大小进行排序，最后将其转换为int数组。

        //影响因素思想，绝对值越大的元素它的影响优先级越高
        nums = IntStream.of(nums)
                    .boxed()
                    .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                    .mapToInt(Integer::intValue)
                    .toArray();
        int len = nums.length;
        //从前向后遍历，遇见负数将其变为正数，同时K--
        for(int i = 0; i < len; i++){
            if(nums[i] < 0 && k > 0){
                nums[i] = -nums[i];
                k--;
            }
        }
        //当取反完成所有负数k还未用完时，现在选取绝对值小的元素取反尽量降低影响，直到将k用完
        //处理思想:若k为偶数，取反两次，值不发生变化；若k为奇数，取反之后值为相反数
        if(k % 2 == 1){
            nums[len - 1] = -nums[len - 1];
        }
        //将数组 nums 转换为流，然后对流中的元素进行求和操作。
        return Arrays.stream(nums).sum();
    }
}

134. 加油站

• 刷题https://leetcode.cn/problems/gas-station/description/
• 文章讲解https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
• 视频讲解https://www.bilibili.com/video/BV1jA411r7WX/?vd_source=af4853e80f89e28094a5fe1e220d9062

• 题解（理解尚有模糊）：

class Solution {
    //贪心方法2:
        //可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，
        //说明各个站点的加油站剩油量rest[i]相加总和一定是大于等于零的。

        //每个加油站的剩余量rest[i]为gas[i] - cost[i]。
        //i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，
        //因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int index = 0;
        for(int i = 0; i < gas.length; i++){
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            //若出现了剩油量为负
            if(curSum < 0){
                //通过取余体现循环数列
                index = (i + 1) % gas.length;
                curSum = 0;
            }
        }
        if(totalSum < 0){
            return -1;
        }
        return index;
    }
}

135. 分发糖果

• 刷题https://leetcode.cn/problems/candy/description/
• 文章讲解https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
• 视频讲解https://www.bilibili.com/video/BV1ev4y1r7wN/?vd_source=af4853e80f89e28094a5fe1e220d9062

• 题解：

class Solution {
    //为了保证不发生混乱需要分别从前往后处理和从后往前处理
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candy = new int[len];
        //初始化第一个孩子最少1个糖果
        candy[0] = 1;
        //从正数第二个开始
        for(int i = 1; i < len; i++){
            candy[i] = (ratings[i] > ratings[i - 1]) ? candy[i - 1] + 1 : 1;
        }
        //从倒数第二个开始
        for(int i = len - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
        //遍历candy获取结果
        int result = 0;
        for(int num : candy){
            result += num;
        }
        return result;
    }
}