25 | 面试题：买卖股票的最佳时机-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 第25章 面试题：买卖股票的最佳时机

在算法面试中，股票买卖问题是一类经典且常考的动态规划或贪心算法问题。这类问题不仅考验了应聘者对算法的理解深度，还检验了其逻辑思维能力和问题解决能力。本章将深入探讨“买卖股票的最佳时机”这一问题，通过详细分析题目要求、解法思路、代码实现及优化策略，帮助读者在面试中从容应对此类难题。

#### 一、题目描述

给定一个数组，它的第 `i` 个元素是一支给定股票第 `i` 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

**注意**：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

#### 二、问题分析

这个问题看似简单，实则蕴含了多种解法思路。首先，我们需要明确题目中的几个关键点：

1. **多次交易**：允许在同一天内多次买卖，但每次买卖之间必须有一个非交易日作为间隔（即不能同时持有两支股票）。
2. **最大化利润**：目标是使通过买卖股票获得的利润最大化。

基于上述分析，我们可以采用以下几种策略来解决这个问题：

- **贪心算法**：由于允许在同一天内多次买卖，我们可以简单地遍历价格数组，累加所有相邻两天之间的正价差（即如果第 `i` 天的价格高于第 `i-1` 天，则计算这两天的价差作为一次交易的利润）。这种方法适用于允许多次交易且没有交易费用的情况。
- **动态规划**：虽然本题通过贪心算法即可解决，但了解动态规划的思路对于处理更复杂的股票买卖问题（如只能进行一次交易、两次交易等）至关重要。

#### 三、解法一：贪心算法

贪心算法的核心思想是，只要今天的价格比昨天高，就选择卖出，并在今天买入（或理解为在昨天买入，今天卖出），以获取这段上涨的利润。由于可以多次交易，我们只需关注每一天与前一天的价差即可。

**代码实现**（Python）：

```python
def maxProfit(prices):
    if not prices:
        return 0
    
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            max_profit += prices[i] - prices[i-1]
    
    return max_profit
```

#### 四、解法二：动态规划（虽非必要，但作为扩展）

虽然本题不需要动态规划，但了解动态规划在股票买卖问题中的应用对于解决更复杂的版本（如只能交易一次、两次等）至关重要。

假设 `dp[i][0]` 表示第 `i` 天交易完后手里没有股票的最大利润，`dp[i][1]` 表示第 `i` 天交易完后手里持有一支股票的最大利润。则有状态转移方程：

- `dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])`：表示第 `i` 天不持股，可以由前一天不持股直接得到，或者前一天持股今天卖出。
- `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`：表示第 `i` 天持股，可以由前一天持股直接得到，或者前一天不持股今天买入。

但注意，由于本题允许无限次交易，且没有交易费，动态规划的状态转移可以简化为贪心策略。

#### 五、扩展问题

- **只能交易一次**：此时需要使用动态规划，且状态转移方程如上所述，但只需考虑 `dp[i][0]`，因为最终目标是最大化不持股时的利润。
- **只能交易两次**：在只能交易一次的基础上，引入一个新的维度或状态来记录已完成的交易次数。
- **含交易费用**：在每次交易时，扣除固定的交易费用，这会影响决策过程，通常需要使用更复杂的动态规划策略。

#### 六、总结

“买卖股票的最佳时机”问题是一类经典的算法面试题，通过贪心算法可以高效地解决允许多次交易且没有交易费用的情况。同时，了解动态规划在股票买卖问题中的应用，有助于解决更复杂的问题变体。在面试中，除了正确实现算法外，清晰地阐述解题思路、分析时间复杂度和空间复杂度也是非常重要的。希望本章内容能帮助读者在面试中脱颖而出，成功通关算法面试。

该分类下的相关小册推荐：

编程之道-算法面试(下)

业务开发实用算法精讲

数据结构与算法(下)

数据结构与算法(上)

数据结构与算法之美

数据结构与算法(中)

编程之道-算法面试(上)