Hot100 贪心算法解析（更新中）

121. 买卖股票的最佳时机

class Solution: def maxProfit(self, prices: List[int]) -> int: ans = 0#最大利润 minprice = prices[0]#最低价格 for price in prices:#遍历每一天的价格 #在遍历过程中，一边记录历史最低价，一边计算当前能获得的最大利润 ans = max(ans,price-minprice)#在当前能卖时尝试更新最大收益 minprice = min(minprice,price)#更新历史最低价 return ans

注意：遍历过程中之所以先更新ans再更新minprice是为了保证 minprice 在 price 之前。

55. 跳跃游戏

class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) max_len = 0#可跳跃的最大位置 for i in range(n): if i>max_len:#如果i在的位置比目前可跳跃的最大位置大，那么肯定不能到下一个下标 return False max_len = max(max_len,nums[i]+i)#可跳跃的最大位置更新 return True

45. 跳跃游戏 II

class Solution: def jump(self, nums: List[int]) -> int: ans = 0#建桥次数（跳跃次数） next_right = 0#下一座桥的右端点的最大值 cur_right = 0#已建造的桥的右端点 n = len(nums) for i in range(n-1): #只遍历到n-2是因为目标是“到达最后一个位置”，如果遍历到 n-1也就是到最后一个点时，还可能触发一次 ans += 1 next_right = max(next_right,i+nums[i])# 遍历的过程中，记录下一座桥的最远点 if cur_right==i: #无路可走，必须建桥 cur_right = next_right#建桥后，最远可以到达 next_right ans+=1 return ans