122. 买卖股票的最佳时机 II
思路：关键点是每一次利用峰值来计算【画图好理解一点，就是计算陡坡的值】！每一次累加和的最大! 或者可以这样理解，把利润划分为每天的，如假如第 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])。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 求峰值的一些问题！关键问题就是找出第一个小值的下标
if len(prices) == 1 or len(prices) == 0:
return 0
min_value = min(prices[0],prices[1])
count = 0
for i in range(0, len(prices) - 1):
if i != 0 and prices[i + 1] < prices[i]:
count += prices[i] - min_value
min_value = prices[i + 1]
if min_value < prices[-1]:
count += prices[-1] - min_value
return count
# 贪心算法
class Solution:
def maxProfit(self, prices: List[int]) -> int:
result = 0
for i in range(1, len(prices)):
result += max(prices[i] - prices[i - 1], 0)
return result
55. 跳跃游戏
思路：问题的核心是将跳几步转化为每次跳跃能覆盖的最大范围！
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
class Solution:
def canJump(self, nums: List[int]) -> bool:
# 进行每次跳跃覆盖的范围
if len(nums) == 1:
return True
index = 0
cover = nums[0]
while index <= cover:
# 更新覆盖范围 只更新比起大的范围
cover = max(index + nums[index], cover)
index += 1
if cover >= len(nums) - 1:
return True
return False
45. 跳跃游戏 II
思路：问题的核心依旧是找出能覆盖的最大的范围，不过需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖【一轮遍历下来就可以了】
class Solution:
def jump(self, nums: List[int]) -> int:
# 依旧是使用覆盖范围，不过是一步一步慢慢来的
if len(nums) == 1:
return 0
# 当前覆盖的的最大距离
cur_distance = 0
# 下一步覆盖的最大距离
next_distance = 0
# 步数
res = 0
# 需要使用到下标了
for i in range(len(nums)):
next_distance = max(i + nums[i], next_distance)
if i == cur_distance:
res += 1
# 更新当前的覆盖距离
cur_distance = next_distance
if cur_distance >= len(nums) - 1:
return res
return res
