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 imax_len:#如果i在的位置比目前可跳跃的最大位置大那么肯定不能到下一个下标 return False max_len max(max_len,nums[i]i)#可跳跃的最大位置更新 return True45. 跳跃游戏 IIclass 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,inums[i])# 遍历的过程中记录下一座桥的最远点 if cur_righti: #无路可走必须建桥 cur_right next_right#建桥后最远可以到达 next_right ans1 return ans