02、买卖股票的最佳时机

厨子大约 13 分钟数据结构算法算法基地面试动态规划刷题程序厨校招社招

这个题目考的老多了，今天就来给大家一块剖析一下这个题目

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/open in new window

题目描述

给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

示例 1:

输入：prices = [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 <= 10^5
0 <= prices[i] <= 10^4

问题理解

关键限制

限制1：只能买卖一次
- 只能完成一笔交易
- 不能多次买卖

限制2：必须先买后卖
- 不能在买入前卖出
- 卖出日期必须在买入日期之后

限制3：买卖在不同天
- 不能当天买当天卖

问题本质

问题：找到 prices[i] 和 prices[j]，使得：
1. j > i （先买后卖）
2. prices[j] - prices[i] 最大（利润最大）

换句话说：
在每个价格，考虑在这一天卖出，
找到之前的最低价格买入，
计算利润并更新最大值。

图解示例

示例：prices = [7,1,5,3,6,4]

索引:   0  1  2  3  4  5
价格:   7  1  5  3  6  4
       ^  ^        ^
       |  |        |
       |  买入     卖出
       不买（太贵）

分析每天卖出的利润：

第 0 天：无法卖出（之前没有买入）
第 1 天：无法卖出（价格 1 是最低点）
第 2 天：在第 1 天买入(1)，第 2 天卖出(5)，利润 = 5-1 = 4
第 3 天：在第 1 天买入(1)，第 3 天卖出(3)，利润 = 3-1 = 2
第 4 天：在第 1 天买入(1)，第 4 天卖出(6)，利润 = 6-1 = 5 ← 最大
第 5 天：在第 1 天买入(1)，第 5 天卖出(4)，利润 = 4-1 = 3

最大利润：5
最佳策略：第 1 天买入，第 4 天卖出

解题思路

方法一：暴力枚举

核心思想

枚举所有可能的买入和卖出日期组合，计算利润。

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int maxProfit = 0;

        // 枚举买入日期
        for (int i = 0; i < n - 1; i++) {
            // 枚举卖出日期（必须在买入之后）
            for (int j = i + 1; j < n; j++) {
                int profit = prices[j] - prices[i];
                maxProfit = max(maxProfit, profit);
            }
        }

        return maxProfit;
    }
};

时间复杂度: O(n²)

空间复杂度: O(1)

缺点: 会超时

方法二：动态规划⭐

核心思想

用 DP 数组记录每一天的两种状态：持有股票和不持有股票。

状态定义：

dp[i][0]: 第 i 天不持有股票时的最大利润
dp[i][1]: 第 i 天持有股票时的最大利润（注意是负数，因为花钱买了）

举个例子吧 dp[2][0] = 3，则代表第 2 天，不持有股票时的最大利润为 3，是否持有是通过上面红色位置的 0 和 1 来区分

DP 五部曲

1. 确定 dp 数组及下标含义
   dp[i][0]: 第 i 天不持有股票的最大利润
   dp[i][1]: 第 i 天持有股票的最大利润（是负数）

2. 确定递推公式
   dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
   dp[i][1] = max(dp[i-1][1], -prices[i])

3. dp 数组如何初始化
   dp[0][0] = 0            # 第0天不持有，利润0
   dp[0][1] = -prices[0]   # 第0天持有，花了prices[0]

4. 确定遍历顺序
   从前往后，i 从 1 到 n-1

5. 举例推导 dp 数组
   见下方详细示例

上述内容不理解的话，继续往下看

状态转移方程详解

理解 dp[i][0] - 第 i 天不持有股票：

两种情况：
1. 昨天就不持有，今天继续不持有（没有买入和卖出操作，利润不变）
   利润 = dp[i-1][0]

2. 昨天持有，今天卖出
   利润 = dp[i-1][1] + prices[i]
   （昨天持有的利润 + 今天卖出得到的钱）

取两种情况的最大值：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])


理解 dp[i][1] - 第 i 天持有股票：

两种情况：
1. 昨天就持有，今天继续持有（没有买入和卖出操作，利润不变）
   利润 = dp[i-1][1]

2. 今天买入（之前没买过，因为只能买一次）
   利润 = -prices[i]
   （买入要花钱，所以是负数）

取最大值：
dp[i][1] = max(dp[i-1][1], -prices[i])

注意：为什么是 -prices[i] 而不是 dp[i-1][0] - prices[i]？
因为题目限制只能买一次，所以买入前的利润一定是 0

详细图解示例

以 prices = [7, 1, 5, 3, 6, 4] 为例：

初始化（每一天都有两种情况，持有和不持有）：
dp[0][0] = 0        # 第0天不持有，利润 = 0
dp[0][1] = -7       # 第0天持有，花了 7 元


第 1 天：价格 = 1

dp[1][0] = max(dp[0][0], dp[0][1] + prices[1])
         = max(0, -7 + 1)
         = max(0, -6)
         = 0
         # 不持有的最大利润是 0（不操作最好）

dp[1][1] = max(dp[0][1], -prices[1])
         = max(-7, -1)
         = -1
         # 持有的最大利润是 -1（今天买更便宜）

dp[1] = [0, -1]


第 2 天：价格 = 5

dp[2][0] = max(dp[1][0], dp[1][1] + prices[2])
         = max(0, -1 + 5)
         = max(0, 4)
         = 4
         # 不持有的最大利润是 4（在第1天买，今天卖）

dp[2][1] = max(dp[1][1], -prices[2])
         = max(-1, -5)
         = -1
         # 持有的最大利润是 -1（保持第1天买入）

dp[2] = [4, -1]


第 3 天：价格 = 3

dp[3][0] = max(dp[2][0], dp[2][1] + prices[3])
         = max(4, -1 + 3)
         = max(4, 2)
         = 4
         # 不持有的最大利润是 4（保持之前的最优）

dp[3][1] = max(dp[2][1], -prices[3])
         = max(-1, -3)
         = -1
         # 持有的最大利润是 -1

dp[3] = [4, -1]


第 4 天：价格 = 6

dp[4][0] = max(dp[3][0], dp[3][1] + prices[4])
         = max(4, -1 + 6)
         = max(4, 5)
         = 5
         # 不持有的最大利润是 5（在第1天买，今天卖）

dp[4][1] = max(dp[3][1], -prices[4])
         = max(-1, -6)
         = -1

dp[4] = [5, -1]


第 5 天：价格 = 4

dp[5][0] = max(dp[4][0], dp[4][1] + prices[5])
         = max(5, -1 + 4)
         = max(5, 3)
         = 5

dp[5][1] = max(dp[4][1], -prices[5])
         = max(-1, -4)
         = -1

dp[5] = [5, -1]


完整 dp 数组：
天数    不持有  持有
0       0      -7
1       0      -1
2       4      -1
3       4      -1
4       5      -1
5       5      -1

最终答案：dp[5][0] = 5 ✓
（第5天不持有股票的最大利润）

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        // dp[i][0]: 第 i 天不持有股票的最大利润
        // dp[i][1]: 第 i 天持有股票的最大利润
        vector<vector<int>> dp(n, vector<int>(2));

        // 初始化第 0 天
        dp[0][0] = 0;           // 第 0 天不持有，利润为 0
        dp[0][1] = -prices[0];  // 第 0 天持有，花费 prices[0]

        // 状态转移
        for (int i = 1; i < n; i++) {
            // 第 i 天不持有：max(昨天就不持有, 昨天持有今天卖)
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);

            // 第 i 天持有：max(昨天就持有, 今天买入)
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }

        // 最后一天不持有股票，利润最大
        return dp[n-1][0];
    }
};

时间复杂度: O(n)，遍历一次数组

空间复杂度: O(n)，二维 dp 数组

空间优化版本⭐⭐

优化思路

观察到 dp[i] 只依赖 dp[i-1]，所以只需要两个变量。

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;

        // 只需要两个变量
        int hold = -prices[0];    // 持有股票的最大利润
        int notHold = 0;          // 不持有股票的最大利润

        for (int i = 1; i < prices.size(); i++) {
            // 更新不持有：max(之前不持有, 卖出)
            int newNotHold = max(notHold, hold + prices[i]);

            // 更新持有：max(之前持有, 买入)
            int newHold = max(hold, -prices[i]);

            // 更新状态
            notHold = newNotHold;
            hold = newHold;
        }

        return notHold;
    }
};

时间复杂度: O(n)

空间复杂度: O(1)（空间优化后）

方法三：一次遍历（最优解，相对来说比 dp 好理解一些）⭐⭐⭐

核心思想

问题转化:

原问题: 找到 prices[j] - prices[i] 的最大值，其中 j > i
转化后: 对于每个价格 prices[j]，如果要在这天卖出，应该在哪天买入才能获得最大利润？
答案: 在 prices[j] 之前的最低价格买入

算法思路:

遍历价格数组，维护两个关键变量：

minPrice: 到目前为止遇到的最低价格（最佳买入时机）
maxProfit: 到目前为止能获得的最大利润

处理流程（对于每个价格）:

更新最低价格: minPrice = min(minPrice, price)
1. 如果当前价格更低，更新最佳买入点
计算今天卖出的利润: profit = price - minPrice
1. 假设在 minPrice 买入，今天卖出
更新最大利润: maxProfit = max(maxProfit, profit)
1. 如果今天卖出利润更大，就更新

算法正确性证明

为什么这个算法是正确的？

关键洞察：
对于第 i 天的价格 prices[i]，如果我们要在这天卖出，
那么最优的买入点一定是 prices[0...i-1] 中的最小值。

证明：
假设在第 i 天卖出，价格为 prices[i]
要使利润 prices[i] - prices[buy] 最大
就需要 prices[buy] 最小
所以 buy 应该选择 prices[0...i-1] 中的最小值索引

算法保证：
- minPrice 总是维护着当前位置之前的最小价格
- 所以对于每个卖出点，我们都用了最优的买入点
- 遍历所有可能的卖出点，就能找到全局最优解

算法流程图

输入: prices = [7, 1, 5, 3, 6, 4]

初始化: minPrice = ∞, maxProfit = 0

遍历每个价格:
    ↓
第 i 天价格 = prices[i]
    ↓
步骤1: minPrice = min(minPrice, prices[i])
  (更新到目前为止的最低价格)
    ↓
步骤2: profit = prices[i] - minPrice
  (计算今天卖出的利润)
    ↓
步骤3: maxProfit = max(maxProfit, profit)
  (更新最大利润)
    ↓
继续下一天

最终返回: maxProfit

详细图解示例

以 prices = [7,1,5,3,6,4] 为例：

初始化：
minPrice = ∞（无穷大）
maxProfit = 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 0 天：价格 = 7

步骤分析：
  更新最低价格：minPrice = min(∞, 7) = 7
  含义：到目前为止，7 是最低价格（最佳买入点）

  计算今天卖出的利润：profit = 7 - 7 = 0
  含义：如果今天买今天卖，利润为 0

  更新最大利润：maxProfit = max(0, 0) = 0
  含义：到目前为止的最大利润是 0

当前状态：minPrice=7, maxProfit=0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 1 天：价格 = 1

步骤分析：
  更新最低价格：minPrice = min(7, 1) = 1
  含义：发现更低价格！最佳买入点更新为第 1 天

  计算今天卖出的利润：profit = 1 - 1 = 0
  含义：如果今天买今天卖，利润为 0

  更新最大利润：maxProfit = max(0, 0) = 0
  含义：最大利润仍然是 0

当前状态：minPrice=1, maxProfit=0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 2 天：价格 = 5

步骤分析：
  更新最低价格：minPrice = min(1, 5) = 1
  含义：最低价格仍然是 1（第 1 天）

  计算今天卖出的利润：profit = 5 - 1 = 4
  含义：如果在第 1 天买入(1)，今天卖出(5)，利润 = 4

  更新最大利润：maxProfit = max(0, 4) = 4
  含义：找到更大利润！更新为 4

当前状态：minPrice=1, maxProfit=4
最佳策略：第 1 天买入(1) → 第 2 天卖出(5)，利润 4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 3 天：价格 = 3

步骤分析：
    更新最低价格：minPrice = min(1, 3) = 1
    含义：最低价格仍然是 1

    计算今天卖出的利润：profit = 3 - 1 = 2
    含义：如果在第 1 天买入，今天卖出，利润 = 2

    更新最大利润：maxProfit = max(4, 2) = 4
    含义：今天卖出利润(2) < 之前最大利润(4)，保持不变

当前状态：minPrice=1, maxProfit=4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 4 天：价格 = 6

步骤分析：
  更新最低价格：minPrice = min(1, 6) = 1
  含义：最低价格仍然是 1

  计算今天卖出的利润：profit = 6 - 1 = 5
  含义：如果在第 1 天买入(1)，今天卖出(6)，利润 = 5

  更新最大利润：maxProfit = max(4, 5) = 5
  含义：找到更大利润！更新为 5

当前状态：minPrice=1, maxProfit=5
最佳策略：第 1 天买入(1) → 第 4 天卖出(6)，利润 5 ⭐

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 5 天：价格 = 4

步骤分析：
  更新最低价格：minPrice = min(1, 4) = 1
  含义：最低价格仍然是 1

  计算今天卖出的利润：profit = 4 - 1 = 3
  含义：如果在第 1 天买入，今天卖出，利润 = 3

  更新最大利润：maxProfit = max(5, 3) = 5
  含义：今天卖出利润(3) < 之前最大利润(5)，保持不变

当前状态：minPrice=1, maxProfit=5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

最终答案：5
最佳策略：第 1 天买入(价格 1) → 第 4 天卖出(价格 6)
最大利润：6 - 1 = 5

关键观察：

minPrice 在第 1 天更新为 1 后，一直保持不变（因为后续都没有更低价格）
maxProfit 在第 2 天首次更新为 4，第 4 天更新为 5
最终最佳策略：在最低价格(1)买入，在最高利润时刻(6)卖出

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;  // 到目前为止的最低价格
        int maxProfit = 0;       // 到目前为止的最大利润

        for (int price : prices) {
            // 更新最低价格
            minPrice = min(minPrice, price);

            // 计算今天卖出的利润
            int profit = price - minPrice;

            // 更新最大利润
            maxProfit = max(maxProfit, profit);
        }

        return maxProfit;
    }
};

时间复杂度: O(n)，只遍历一次数组

空间复杂度: O(1)，只用两个变量

02、买卖股票的最佳时机

# 题目描述

# 问题理解

# 关键限制

# 问题本质

# 图解示例

# 解题思路

# 方法一：暴力枚举

# 核心思想

# 代码实现

# 方法二：动态规划⭐

# 核心思想

# DP 五部曲

# 状态转移方程详解

# 详细图解示例

# 代码实现

# 空间优化版本⭐⭐

# 优化思路

# 代码实现

# 方法三：一次遍历（最优解，相对来说比 dp 好理解一些）⭐⭐⭐

# 核心思想

# 算法正确性证明

# 算法流程图

# 详细图解示例

# 代码实现

题目描述

问题理解

关键限制

问题本质

图解示例

解题思路

方法一：暴力枚举

核心思想

代码实现

方法二：动态规划⭐

核心思想

DP 五部曲

状态转移方程详解

详细图解示例

代码实现

空间优化版本⭐⭐

优化思路

代码实现

方法三：一次遍历（最优解，相对来说比 dp 好理解一些）⭐⭐⭐

核心思想

算法正确性证明

算法流程图

详细图解示例

代码实现