算法训练营day29 | {122.买卖股票的最佳时机II, 55.跳跃游戏, 45.跳跃游戏II, 1005.K次取反后最大化的数组和}

第八章贪心算法part02，贪心的思路，局部最优贪在哪里。

122. 买卖股票的最佳时机II

1.1 解题分析

本题如果想到最终利润是可以分解的，那就容易了（只收集正利润，局部最优推出全局最优）。如何分解？
假设第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]，相当于 (price[3] - price[2]) + (price[2] - price[1]) + (price[1] - price[0])，此时就把利润分解为每天为单位的维度，不用从第0天到第3天整体去考虑。

1
2
3
4
5
6
7
8
9
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}

55. 跳跃游戏

2.1 解题分析

Jump Game 不是“从 cover 再跳”，而是“枚举所有能站到的位置 i，从 i 再跳”。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean canJump(int[] nums) {
        int cover = nums[0];
        for (int i = 0; i <= cover; i++) {
           cover = Math.max(cover, i + nums[i]);
           if (cover >= nums.length - 1) return true;
        }
        return false;
    }
}

45. 跳跃游戏II

3.1 解题分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int result = 0;
        int cur = 0;
        int next = 0;
        for (int i = 0; i < nums.length; i++) {
            next = Math.max(next, i + nums[i]);
            if (i == cur) {
                result++;
                cur = next;
                if (cur >= nums.length - 1) break;
            }
        }
        return result;
    }
}

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

4.1 解题分析

培养用贪心的思考方式（局部最优，全局最优）来解题。局部最优：让绝对值最大的负数变为正数。

  • 注意第一遍写的时候，k还有剩并且是奇数的情况下，反转绝对值最小的数，因为一开始没有按照绝对值大小来排序，所以还得再排序一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }

        if (k % 2 == 1) {
            int minIndex = 0;
            for (int i = 1; i < nums.length; i++) {
                if (Math.abs(nums[i]) < Math.abs(nums[minIndex])) minIndex = i;
            }
            nums[minIndex] = -nums[minIndex];
        }
        return Arrays.stream(nums).sum();
    }
}
Leetcode > 贪心算法
#Java #代码随想录
算法训练营day29 | {122.买卖股票的最佳时机II, 55.跳跃游戏, 45.跳跃游戏II, 1005.K次取反后最大化的数组和}
http://paopaotangzu.xyz/cn/day29_leetcode/
作者
PROTON TANG
发布于
2026年1月14日
许可协议