第二十八天|贪心算法|122.买卖股票的最佳时机II，55. 跳跃游戏，45.跳跃游戏II，1005.K次取反后最大化的数组和

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

方法1：贪心算法（简单）

方法2：动态规划

55. 跳跃游戏

45.跳跃游戏II

方法1

方法2（简洁版）

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

按照绝对值大小从大到小排序一次

两次排序Arrays.sort()

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

方法1：贪心算法（简单）

思路：

只有一只股票
当前只有买股票或者卖股票的操作

想获得利润至少要两天为一个交易单元。

分解利润

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

那么只收集正利润就是贪心所贪的地方！

局部最优：收集每天的正利润，全局最优：求得最大利润。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

    class Solution {public int maxProfit(int[] prices) {int res = 0;for (int i = 1; i < prices.length; i++) {res += Math.max(prices[i] - prices[i - 1], 0);}return res;}}

方法2：动态规划

下一章详解。也挺好理解的，看下代码就行。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

    class Solution {public int maxProfit(int[] prices) {// 方法2：动态规划// [天数][是否持有股票]int[][] dp = new int[prices.length][2];dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < prices.length; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[prices.length - 1][0];}}

55. 跳跃游戏

这道题目关键点在于：不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。

思路：

这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

时间复杂度: O(n)
空间复杂度: O(1)

    class Solution {public boolean canJump(int[] nums) {if (nums.length == 1) {return true;}//覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的int coverRange = 0;for (int i = 0; i <= coverRange; i++) {coverRange = Math.max(coverRange, i + nums[i]);if (coverRange >= nums.length - 1) {return true;}}return false;}}

45.跳跃游戏II

本题相对于55.跳跃游戏还是难了不少。

但思路是相似的，还是要看最大覆盖范围。

本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一呢？

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

方法1

从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。

时间复杂度: O(n)
空间复杂度: O(1)

需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖

    class Solution {public int jump(int[] nums) {// 方法1if (nums.length == 1) {return 0;}int curDistance = 0; //当前的覆盖最大区域int count = 0; //记录跳跃的次数int maxDistance = 0; //最大的覆盖区域for (int i = 0; i < nums.length; i++) {//在可覆盖区域内更新最大的覆盖区域maxDistance = Math.max(maxDistance, i + nums[i]);//说明当前一步，再跳一步就到达了末尾if (maxDistance >= nums.length - 1) {count++;break;}//走到当前覆盖的最大区域时，更新下一步可达的最大区域if (i == curDistance) {curDistance = maxDistance;count++;}}return count;}}

方法2（简洁版）

依然是贪心，思路和方法一差不多，代码可以简洁一些。

针对于方法1的特殊情况，可以统一处理，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。

想要达到这样的效果，只要让移动下标，最大只能移动到 nums.size - 2 的地方就可以了。

因为当移动下标指向 nums.size - 2 时：

如果移动下标等于当前覆盖最大距离下标，需要再走一步（即 ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：

如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：

时间复杂度: O(n)
空间复杂度: O(1)

其精髓在于控制移动下标 i 只移动到 nums.size() - 2 的位置，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不用考虑别的了。

    class Solution {public int jump(int[] nums) {// 方法2 简化版int result = 0;// 当前覆盖的最远距离下标int end = 0;// 下一步覆盖的最远距离下标int temp = 0;// i <= end：我们只能遍历到当前跳跃范围（end）内的元素，超出end的元素在这次跳跃范围内是无法到达的。// end < nums.length - 1：我们只需要跳到或超过最后一个位置即可，因此只要end没到达最后一个位置，就需要继续跳跃。for (int i = 0; i <= end && end < nums.length - 1; i++) {temp = Math.max(temp, i + nums[i]); // 计算能到达的最远位置// 可达位置的改变次数就是跳跃次数if (i == end) { // 更新跳跃次数end = temp;result++;}}return result;}}

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

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让数组和达到最大。

又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大，全局最优：整个数组和达到最大

两次贪心！

那么本题的解题步骤为：

第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K--
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和

时间复杂度: O(nlogn)
空间复杂度: O(1)

按照绝对值大小从大到小排序一次

    class Solution {public int largestSumAfterKNegations(int[] nums, int k) {// 绝对值大小排序// 方法1，麻烦计算
//            nums = IntStream.of(nums)
//                    .boxed()
//                    .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
//                    .mapToInt(Integer::intValue).toArray();
//            int sum = 0;
//            for (int i = 0; i < nums.length; i++) {
//                if (nums[i] < 0 && k > 0) {
//                    nums[i] = -nums[i];
//                    k--;
//                }
//                sum += nums[i];
//            }
//            if (k % 2 != 0){
//                sum -= 2 * nums[nums.length-1];
//            }
//            return sum;// 绝对值大小排序// 方法2，借助stream// 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();int len = nums.length;for (int i = 0; i < len; i++) {//从前向后遍历，遇到负数将其变为正数，同时K--if (nums[i] < 0 && k > 0) {nums[i] = -nums[i];k--;}}// 如果K还大于0，那么反复转变数值最小的元素，将K用完if (k % 2 == 1) {nums[len - 1] = -nums[len - 1];}return Arrays.stream(nums).sum();}}

两次排序Arrays.sort()

    class Solution {public int largestSumAfterKNegations(int[] nums, int k) {// 方法3：排序数组并贪心地尽可能将负数翻转为正数，再根据剩余的k值调整最小元素的符号，从而最大化数组的总和。if (nums.length == 1) {return nums[0]; // 有点奇怪，不管k？}// 排序：先把负数处理了Arrays.sort(nums);for (int i = 0; i < nums.length && k > 0; i++) { // 贪心点, 通过负转正, 消耗尽可能多的kif (nums[i] < 0) {nums[i] = -nums[i];k--;}}// 退出循环, k > 0 || k < 0 (k消耗完了不用讨论)if (k % 2 == 1) { // k > 0 && k is odd：对于负数：负-正-负-正Arrays.sort(nums);// 再次排序得到剩余的负数，或者最小的正数nums[0] = -nums[0];}int sum = 0;for (int num : nums) {sum += num;}return sum;}}

此题虚注意：先处理好数组后最后再同意进行求和会方便一点，逻辑也清晰一点。

第二十八天的总算是结束了，直冲Day29！