【贪心算法2】

力扣122.买卖股票最佳时机Ⅱ

链接: link

思路

要求最大利润，可以分解成子问题求解，在最低价格买入，最高价格卖出。
假如第0天价格最低，第3天价格最高，利润=prices[3] - pricnes[0],
可以将利润公式拆解成
(prices[3]-prices[2])+(prices[2]-prices[1])+(prices[1]-prices[0])
最终变成了求相邻两天的利润，所以可以得到一个关于利润的列表，只需要将这个列表大于0的相加即可求出最大利润

方法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;
    }
}

相似题型

思路

上一道题是求利润最大化，而这道题是只能进行一次买卖，要求这一次利润最大
121.买卖股票的最佳时机
链接: link

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int minPrice = prices[0];
        for (int p : prices) {
            res = Math.max(res, p - minPrice);
            minPrice = Math.min(minPrice, p);
        }
        return res;
    }
}

55.跳跃游戏
链接: link

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1) return true;
        int cover = 0;
        for(int i =0;i<=cover;i++){
            cover = Math.max(i + nums[i],cover);
            if(cover >= nums.length - 1){
                return true;
            }
        }
        return false;
    }
}

45.跳跃游戏Ⅱ

思路

这道题需要记录2个距离，一个是当前位置能走的最大距离和下一步能走的最大距离，当下一步能走的最大距离覆盖终点即为最优解。注意要先更新下一步最大距离，当i=当前最大距离时再更新当前最大距离。
链接: link

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1)
            return 0;
        int cover_1 = 0; // 当前位置的覆盖范围
        int cover_2 = 0; // 下一个位置的覆盖范围
        int cnt = 0; // 记录跳次数
        for (int i = 0; i < nums.length; i++) {
            cover_2 = Math.max(i + nums[i], cover_2);
            // 此时只需要走一步即可到达终点
            if (cover_2 >= nums.length - 1) {
                cnt++;
                break;
            }
            // 走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i == cover_1) {
                cover_1 = cover_2;
                cnt++;
            }
        }
        return cnt;
    }
}