贪心算法的核心，就是用局部最优去代替全局最优。
一般的步骤就是去试思路，然后举反例，如果举不出反例，基本可以看作是正确的方法。
121. 买卖股票的最佳时机（Best Time to Buy and Sell Stock）
难度： 简单
题目描述：
给定一个数组，它的第 i 个元素是某支股票第 i 天的价格。你可以选择某一天买入该股票，并在未来某一天卖出股票，求最大利润。你不能在买入股票之前卖出股票。
示例：
输入：
[7, 1, 5, 3, 6, 4]输出：
5
解释： 在第 2 天（价格 = 1）买入，在第 5 天（价格 = 6）卖出，最大利润为6 - 1 = 5。输入：
[7, 6, 4, 3, 1]输出：
0
解释： 在这个情况下, 没有交易发生, 所以最大利润是0。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
minprice = float('inf')
res = 0
for i in range(len(prices)):
if prices[i] < minprice:
minprice = prices[i]
res = max(res,prices[i] - minprice)
return res这道题可以用折线图来表示:
55. 跳跃游戏（Jump Game）
难度： 中等
题目描述：
给定一个非负整数数组 nums，其中每个元素表示你在该位置可以跳跃的最大长度。判断你是否能够从数组的第一个位置跳到最后一个位置。你可以跳跃的最大长度随时变化，但每次只能跳跃一次。
示例：
输入：
[2, 3, 1, 1, 4]输出：
true
解释： 从第 1 个位置开始，你可以跳跃到第 2 个位置，再跳跃到第 4 个位置，从而到达最后一个位置。输入：
[3, 2, 1, 0, 4]输出：
false
解释： 无论你从哪个位置开始，都无法到达最后一个位置。
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0
for i in range(len(nums)):
if i > cover:
return False
cover = max(cover,i+nums[i])
return True
45. 跳跃游戏 II（Jump Game II）
难度： 中等
题目描述：
给定一个非负整数数组 nums，其中每个元素表示你在该位置可以跳跃的最大长度。你需要找到从数组的第一个位置跳到最后一个位置的最小跳跃次数。
示例：
输入：
[2, 3, 1, 1, 4]输出：
2
解释： 最小跳跃次数是 2。你可以从第 1 个位置跳到第 2 个位置，再跳跃到第 5 个位置。输入：
[1, 2, 3, 4, 5]输出：
3
解释： 最小跳跃次数是 3。你可以从第 1 个位置跳到第 2 个位置，再跳跃到第 4 个位置，最后到达最后一个位置。
class Solution:
def jump(self, nums: List[int]) -> int:
cover = 0
jump = 0
cur_end = 0
for i in range(len(nums)-1):
cover = max(cover,i+nums[i])
if i == cur_end:
jump += 1
cur_end = cover
return jump
这道题的与上一道题的不同点在于，这道题一定能够到达终点。
cover依然代表覆盖的最大范围。
jump代表次数，而cur_end代表当前这一跳的最远距离，一旦到达这一跳最远距离，就需要往下一跳去了，这时候就要更新下一跳的最远距离为当前的cover最远。
763. 划分字母区间（Partition Labels）
难度： 中等
题目描述：
给定一个字符串 S，将字符串分成尽可能多的部分，使得每个字母只出现在一个部分。返回一个表示每个部分的大小的列表。
示例：
输入：
"ababcbacadefegdehijhklij"输出：
[9, 7, 8]
解释：
按照如下划分：
"ababcbaca"包含了字母'a','b','c'。
"defegde"包含了字母'd','e','f','g'。
"hijhklij"包含了字母'h','i','j','k','l'。输入：
"eccbbbbdec"输出：
[10]
解释： 字符串只有一个区间。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
# 记录每个字符最后的位置
last = {c:i for i,c in enumerate(s)}
res = []
start = end = 0
for i,c in enumerate(s):
end = max(end,last[c])
if end == i:
res.append(end - start +1)
start = i + 1
return res有个式子需要记住：
last = {c:i for i,c in enumerate(s)}遍历一遍之后，记录了每个字符的最后出现的位置。
和跳跃位置2一样，到达当前最远了，就应该更新了。
