121.买卖股票的最佳时机#

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：Awesome Golang Algorithm

题目描述#

题目地址 代码

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

提示

只能卖一次股票

示例 1#

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2#

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

限制#

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

题解#

我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。形式上，对于每组 i 和 j（其中 j > i）我们需要找出 \( \max(prices[j]−prices[i]) \)。

思路 1：暴力循环#

算法流程：

2 次循环分别找出最大价格和最小价格

复杂度分析：

  • 时间复杂度: \( \Omicron(N^{2}) \) , 循环运行 \( \cfrac{n (n-1)}{2} \) 次。
  • 空间复杂度: \( \Omicron(1) \) , 只使用了常数个变量。

代码#

```go func maxProfit_1(prices []int) int { ans := 0 for i := 0; i < len(prices); i++ { for j := i + 1; j < len(prices); j++ { ans = max(ans, prices[j]-prices[i]) } } return ans } ```

思路 2：贪心#

算法流程#

leetcode_121_2

因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

复杂度分析#

  • 时间复杂度: \( \Omicron(N) \)
  • 空间复杂度: \( \Omicron(1) \)
```go func maxProfit_2(prices []int) int { ans, lowPrice := 0, prices[0] for i := 0; i < len(prices); i++ { ans = max(ans, prices[i]-lowPrice) lowPrice = min(lowPrice, prices[i]) } return ans } ```

思路 3：动态规划#

算法流程#

  • 确定 dp 数组（Dynamic Planning）以及下标的含义：
\( \begin{dcases} dp[i][0] & 第 i 天持有股票所得最多现金 \\ dp[i][1] & 第 i 天不持有股票所得最多现金 \end{dcases} \)
  • 确定递推公式
flowchart LR
    A[第 i 天是否持有股票] -->|持有| B(第 i-1 天是否持有股票)
    A[第 i 天是否持有股票] -->|未持有| C(第 i-1 天是否持有股票)
    B -->|持有| D["保存不动：dp[i - 1][0]"]
    B -->|未持有| E["购买股票：-prices[i]"]
		C -->|持有| F["保存不动：dp[i - 1][1]"]
    C -->|未持有| G["购买股票：prices[i] + dp[i - 1][0]"]
\( \begin{dcases} dp[i][0] = \max(dp[i-1][0], -prices[i]) \\ dp[i][1] = \max(dp[i-1][1], dp[i-1][0]+prices[i]) \end{dcases} \)
  • dp 数组如何初始化
\( \begin{dcases} dp[0][0] = -prices[0] \\ dp[0][1] = 0 \end{dcases} \)
  • 确定遍历顺序
\( \int_{prices_i}\ 1<=i<len(prices)-1 \)
  • 举例推导 dp 数组，输入：[7,1,5,3,6,4]
\( \begin{bmatrix} i & dp[i][0] & dp[i][1] \\ 0 & -7 & 0 \\ 1 & -1 & 0 \\ 2 & -1 & 4 \\ 3 & -1 & 4 \\ 4 & -1 & 5 \\ 5 & -1 & \boxed{5} \\ \end{bmatrix} \)

复杂度分析#

  • 时间复杂度: \( \Omicron(N) \)
  • 空间复杂度: \( \Omicron(N) \)
```go func maxProfit_3(prices []int) int { dp, n := make([][2]int, len(prices)), len(prices) dp[0][0], dp[0][1] = -prices[0], 0 for i := 1; i < n; i++ { dp[i][0] = max(dp[i-1][0], -prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]) } return dp[n-1][1] } ```

总结#

…

Backward 0101-0200 122.买卖股票的最佳时机 II Forward