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