目錄

121.買賣股票最佳時機

題目描述

示例

算法分析

代碼(python3)

122.買賣股票最佳時機II

?題目描述

示例

算法分析

代碼（python3）

55.跳躍游戲

題目描述

示例

算法分析

代碼

45.跳躍游戲II

題目描述

示例

算法分析

代碼

---

121.買賣股票最佳時機

題目描述

給定一個數組 prices ，它的第?i 個元素?prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

示例

輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
? ? ?注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

這個問題實際上是利用了“貪心算法”的思想。

算法分析

這個算法的目的是找出股票交易中的最大利潤，即買入和賣出股票的最佳時機。算法的核心思想是：

1. 維護一個最小值（mn）：這個變量用于記錄遍歷過的價格中的最小值。這相當于我們在尋找買入股票的最佳時機（即價格最低的時候）。
2. 計算利潤（ans）：對于每一個價格，我們計算如果在這個價格賣出股票，那么利潤是多少（即當前價格減去之前記錄的最小值）。然后，我們更新記錄的最大利潤（ans）。

為什么說是貪心算法？

• 局部最優選擇：在每一步，我們都選擇到目前為止看到的最小值作為可能的買入點，這是一個局部最優選擇，因為我們假設在這一點上買入可以最大化后續可能的利潤。
• 無回溯：一旦我們選擇了某個點作為“可能的買入點”，我們就不會回頭去改變這個選擇（除非遇到一個更低的價格）。這符合貪心算法“一旦做出選擇，不再更改”的特點。

代碼(python3)

class Solution:def maxProfit(self, prices: List[int]) -> int:# mn用來記錄前n個最小的值mn = prices[0]# ans用來記錄前n個最小的值與當前值的差值的最大值ans = 0for x in prices:mn = min(mn,x)ans = max(ans,x-mn)return ans

122.買賣股票最佳時機II

?題目描述

給你一個整數數組 prices ，其中?prices[i] 表示某支股票第 i 天的價格。

在每一天，你可以決定是否購買和/或出售股票。你在任何時候?最多?只能持有 一股 股票。你也可以先購買，然后在 同一天 出售。

返回 你能獲得的 最大 利潤?

示例

輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4。
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3。
最大總利潤為 4 + 3 = 7 。

算法分析

遍歷數組，如果當天買入第二天會漲，就在第二天賣出。否則當天就不買入。這個方法，最終利潤是最大的。

代碼（python3）

class Solution:def maxProfit(self, prices: List[int]) -> int:profit = 0for i in range(1, len(prices)):tmp = prices[i] - prices[i - 1]if tmp > 0:profit += tmpreturn profit

55.跳躍游戲

題目描述

給你一個非負整數數組?nums ，你最初位于數組的 第一個下標 。數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標，如果可以，返回 true ；否則，返回 false 。

示例

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。

算法分析

遍歷每一項,如果當前位置能到達并且大于前面所能到達的最大位置，就更新最大位置

代碼

class Solution:def canJump(self, nums: List[int]) -> bool:# 遍歷每一項max_i = 0for i,jump in enumerate(nums):# 如果當前位置能到達并且大于前面所能到達的最大位置，就更新最大位置if max_i>=i and i+jump>max_i:max_i = i+jumpreturn max_i>=len(nums)-1

45.跳躍游戲II

題目描述

給定一個長度為 n 的 0 索引整數數組 nums。初始位置為 nums[0]。
每個元素 nums[i] 表示從索引 i 向后跳轉的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:

? 0 <= j <= nums[i]?
? i + j < n
返回到達?nums[n - 1] 的最小跳躍次數。生成的測試用例可以到達 nums[n - 1]。

示例

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是2，從下標為 0 跳到下標為 1 的位置，跳?1步，然后跳3步到達數組的最后一個位置。

算法分析

想象有一條河，0和m一1分別是河的兩岸。一開始，你在0，要到n-1。

把區間[i,i+nums[i]]視作一座橋。一開始只能建一座橋，也就是[0，nums[0]]。比如建造了一座從0到4的橋。

下一座橋要選哪個呢？

在可以選的橋中，選擇右端點最大的橋。它會讓你走的更遠。

重復該過程，到達n-1時退出循環。修建的橋的數量就是答案。

代碼

class Solution:def jump(self, nums: List[int]) -> int:ans = 0cur_right = 0  # 已建造的橋的右端點next_right = 0  # 下一座橋的右端點的最大值for i in range(len(nums) - 1):# 遍歷的過程中，記錄下一座橋的最遠點next_right = max(next_right, i + nums[i])if i == cur_right:  # 無路可走，必須建橋cur_right = next_right  # 建橋后，最遠可以到達 next_rightans += 1return ans