LeetCode 热题 100（八）：贪心。121. 买卖股票的最佳时机、45. 跳跃游戏 II

题目一：

121. 买卖股票的最佳时机https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

思路：因为时间复杂度O（n），所以使用贪心来做。类似双指针，一个指针记录到当前循环时最小的股票价格，另一个记录最大利润（每次都用prices[i] - 前一个指针值，并取max）

代码：

class Solution {
    public int maxProfit(int[] prices) {
        // 记录最小值
        int low = Integer.MAX_VALUE;
        // 记录最大利润
        int high = 0;
        for (int i = 0; i < prices.length; i++) {
            low = Math.min(low, prices[i]);
            high = Math.max(prices[i] - low, high);
        }
        return high;
    }
}

题目二：

45. 跳跃游戏 IIhttps://leetcode.cn/problems/jump-game-ii/

思路：贪心。需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

首先求出下一步最大覆盖的最大值，如果可以到达终点，直接count+1；

若不能到达终点，则让当前这一步最大覆盖＝下一步最大覆盖的最大值，继续重复求当前这一步的下一步覆盖最大值。

图片来源：代码随想录

代码：

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 0 || nums.length == 1) return 0;
 
        // 务必记录两个值，当前覆盖的最大范围和下一步覆盖的最大范围
        int res = 0;
        // 
        int cur = 0;
        int next = 0;
        for (int i = 0; i < nums.length; i++) {
            next = Math.max(next, nums[i] + i);
            if (next >= nums.length - 1)
                return res + 1;
            if (i == cur){
                res++;
                cur = next;
            }
        }
        return res;
    }
}