---
title: "122. Best Time to Buy and Sell Stock II"
url: "https://laigary.com/interview/coding/122-best-time-to-buy-and-sell-stock-ii"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Greedy", "Dynamic Programming", "Classic"]
---

# 122. Best Time to Buy and Sell Stock II

[122\. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)

這個題目是每天都可以買賣股票，但是最多只能同時持有一股的股票，要買之前要先賣掉股票。

## 思路

**這一題改的旋鈕是「交易次數變成無限」。** 完整的狀態機和其他五題的對照見 [股票買賣家族模板](/interview/coding/stock-template)。

`k` 無限帶來一個很好的簡化：**狀態裡不需要記「還剩幾次」了** —— 因為「還剩無限次」和「用掉一次之後還剩無限次」是同一個狀態。所以 [121](/interview/coding/121-best-time-to-buy-and-sell-stock) 的三維狀態在這裡塌成兩個變數：手上有股票、手上沒股票。

### 還有一個更短的貪心解

因為次數無限，這題其實有一個一眼就能寫的解法：

> **把所有上漲的區段全部吃下來。**

只要明天比今天貴，就今天買明天賣。看起來像作弊，但它是對的 —— 因為連續上漲 `a → b → c` 拆成兩筆交易 `(b-a) + (c-b)` 和一筆 `(c-a)` 獲利完全相同，而次數無限所以拆開不用付代價。下跌的區段則一律跳過（不參與，獲利 0）。

```python
        return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))
```

面試時兩個都值得講：**貪心版展示你看穿了題目的結構，DP 版展示你能推廣到其他五題**。如果只給貪心解，面試官接著問 123（限兩次）就會卡住，因為貪心在有次數限制時不成立。

## 解題方向

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0

        buys = [float('-inf')] * len(prices) 
        sells = [0] * len(prices) 
        buys[0] = -prices[0]

        for i in range(1, len(prices)):
            buys[i] = max(buys[i-1], sells[i-1] - prices[i])
            sells[i] = max(sells[i-1], buys[i-1] + prices[i])

        return sells[-1]
```

兩行轉移就是狀態機的直譯：

- `buys[i]`（今天結束時**持有**股票的最大獲利）= 昨天就持有，或昨天沒持有、今天買進
- `sells[i]`（今天結束時**不持有**）= 昨天就不持有，或昨天持有、今天賣出

`buys` 初始化成 `-inf` 是哨兵：「第 0 天之前就持有股票」不是合法狀態，用 `-inf` 讓 `max` 自動淘汰它。

另一版把第 0 天的初始化搬進迴圈裡：

```python
        for i in range(len(prices)):
            if i == 0:
                buys[i] = max(buys[i], 0 - prices[i])
            else:
                buys[i] = max(buys[i-1], sells[i-1] - prices[i])
            sells[i] = max(sells[i-1], buys[i-1] + prices[i])
```

兩種等價。**兩個陣列其實都可以省掉**，因為轉移只看前一天：

```python
        buys, sells = float('-inf'), 0
        for price in prices:
            buys = max(buys, sells - price)
            sells = max(sells, buys + price)
        return sells
```

這裡有個看起來危險但其實無害的細節：`sells` 用的是**同一輪剛更新過的 `buys`**。等於允許「今天買、今天賣」，但那筆交易獲利是 0，不會讓答案變大 —— 所以結果仍然正確。（在 [309 冷凍期](/interview/coding/309-best-time-to-buy-and-sell-stock-with-cool-down) 那題就不能這樣偷懶了。）

## 補充

**整個家族的對照**見 [股票買賣家族模板](/interview/coding/stock-template)。這題和 [309](/interview/coding/309-best-time-to-buy-and-sell-stock-with-cool-down)、[714](/interview/coding/714-best-time-to-buy-and-sell-stock-with-transaction-fee) 是同一組（都是 `k` 無限），差別只在多了冷凍期或手續費 —— 三題的程式碼幾乎一樣，值得一起看。

**貪心能用的條件**值得單獨記住：次數無限、沒有冷凍期、沒有手續費。加上任何一個限制，貪心就不成立，必須回到狀態機。

## 複雜度

**動態規劃**
- 時間 $O(n)$ — 一趟迴圈，每天常數次計算
- 空間 $O(n)$ 用陣列、$O(1)$ 用滾動變數

**貪心**
- 時間 $O(n)$ — 一趟
- 空間 $O(1)$

其中 `n` 是天數。兩者同級，**貪心的常數更小也更短，但只適用這一題**。