貪心算法的核心，就是用局部最優去代替全局最優。

一般的步驟就是去試思路，然后舉反例，如果舉不出反例，基本可以看作是正確的方法。

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 = 0for 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 Falsecover = 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 = 0jump = 0cur_end = 0for i in range(len(nums)-1):cover = max(cover,i+nums[i])if i == cur_end:jump += 1cur_end = coverreturn 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 = 0for i,c in enumerate(s):end = max(end,last[c])if end == i:res.append(end - start +1)start = i + 1return res

有個式子需要記住：

      last = {c:i for i,c in enumerate(s)}

遍歷一遍之后，記錄了每個字符的最后出現的位置。

和跳躍位置2一樣，到達當前最遠了，就應該更新了。