【代码随想录Day33】贪心算法/DP

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

https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

思想是对从小到大的负数，依次变号，全部负数变完后如果还有多的，则反复变号绝对值最小的那个数，这个数可能以前是最大的负数或者最小的正数。

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int idx = 0;
        for (int i = 0; i < k; i++) {
            if (idx < nums.length - 1 && nums[idx] < 0) { //既需要变负为正，又需要和后面的数比绝对值的数
                nums[idx] *= -1;
                if (nums[idx] >= Math.abs(nums[idx + 1])) idx++;  //对最后一个负数来说，要和第一个正数比绝对值，保证idx停在小的那个上
                continue;
            }
            nums[idx] *= -1;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}

134 加油站

https://leetcode.cn/problems/gas-station/description/

gasLeft是到达i + 1时还剩的油，min of gasLeft是终点last

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int last = 0;
        int minLevel = Integer.MAX_VALUE;      //find when arrive at which station the gasLeft is the lowest
        int gasLeft = 0;
        for (int i = 0; i < gas.length; i++) {
            gasLeft = gasLeft + gas[i] - cost[i];  // gasLeft是到达i + 1时还剩的油，min of gasLeft是终点last
            if (gasLeft <= minLevel) {   //bug 水平段要取最后一个点
                minLevel = gasLeft;
                last = i;
            }
        }
        if (gasLeft < 0) return -1;
        return last + 1 == gas.length ? 0 : last + 1;
    }
}

135 分发糖果

https://leetcode.cn/problems/candy/description/

正着走一次检查矫正一个方向，反着再走一次矫正。

class Solution {
    public int candy(int[] ratings) {
        int[] candy = new int[ratings.length];
        Arrays.fill(candy, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = Math.max(candy[i], candy[i - 1] + 1);
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int num : candy) {
            sum += num;
        }
        return sum;
    }
}