Best Time to Buy and Sell Stock with Transaction Fee
題目描述
給定每日股價陣列 prices 和交易手續費 fee。可以進行無限次交易（一次買入+賣出=一次交易），但每次交易要付 fee。不能同時持有多股。回傳最大利潤。
輸入：prices = [1,3,2,8,4,9], fee = 2
輸出：8
解釋：第0天買入(1)，第3天賣出(8)，利潤=8-1-2=5；第4天買入(4)，第5天賣出(9)，利潤=9-4-2=3；總利潤=8
解題思路
定義兩個狀態
hold = 持有股票時的最大利潤，cash = 不持有股票時的最大利潤。每天在這兩個狀態間轉移
初始化
cash = 0（第一天不操作），hold = -prices[0]（第一天買入，花了 prices[0] 元，利潤為負）
每天轉移
newCash = max(cash, hold + price - fee)（觀望 vs 賣出扣手續費），newHold = max(hold, cash - price)（持有 vs 買入）
最終答案
回傳最後一天的 cash。最後手上不持有股票一定比持有更好（持有代表還沒賣）
程式碼
C#
public class Solution {
public int MaxProfit(int[] prices, int fee) {
int cash = 0; // 不持有股票的最大利潤
int hold = -prices[0]; // 持有股票的最大利潤
for (int i = 1; i < prices.Length; i++) {
int newCash = Math.Max(cash, hold + prices[i] - fee);
int newHold = Math.Max(hold, cash - prices[i]);
cash = newCash;
hold = newHold;
}
return cash;
}
}TypeScript
function maxProfit(prices: number[], fee: number): number {
let cash = 0;
let hold = -prices[0];
for (let i = 1; i < prices.length; i++) {
const newCash = Math.max(cash, hold + prices[i] - fee);
const newHold = Math.max(hold, cash - prices[i]);
cash = newCash;
hold = newHold;
}
return cash;
}Python
def maxProfit(prices: list[int], fee: int) -> int:
cash = 0 # 不持有股票
hold = -prices[0] # 持有股票
for price in prices[1:]:
new_cash = max(cash, hold + price - fee) # 賣出或觀望
new_hold = max(hold, cash - price) # 買入或繼續持有
cash, hold = new_cash, new_hold
return cash複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
遍歷價格陣列一次，每天做兩次 max 比較（常數操作），因此時間 O(n)。只用 cash 和 hold 兩個變數追蹤狀態，空間 O(1)。
邊界情況
- 只有一天：無法完成買賣，cash = 0，回傳 0
- 價格一路上漲：例如
[1,2,3,4,5], fee=1，最佳策略是第 0 天買、最後一天賣，利潤 = 5-1-1 = 3（一次交易比多次交易省手續費） - 手續費很高：如果 fee 大於任意兩天的價差，不做任何交易，回傳 0
圖解
圖表展示狀態機的兩個狀態和四種轉移：Cash 狀態可以買入（轉到 Hold）或觀望（留在 Cash），Hold 狀態可以賣出扣手續費（轉到 Cash）或繼續持有（留在 Hold）。每天在兩個狀態上各取最優選擇。
進階觀點
💡面試追問
-
Q: 股票系列題有統一框架嗎？ A: 有，用狀態機 DP，以 (天數, 交易次數, 持有狀態) 三個維度定義狀態。121（一次交易）、122（無限次無手續費）、123（最多兩次）、188（最多 K 次）、309（有冷凍期）、714（有手續費）都用同樣的框架，只是轉移方程的約束不同。
-
Q: 為什麼需要 newCash / newHold 暫存？ A: 因為 cash 和 hold 的更新公式互相依賴：
newCash用舊的 hold，newHold用舊的 cash。如果先更新 cash 再用它算 hold，hold 用到的就是新值而非舊值，結果會錯。Python 可以用cash, hold = max(...), max(...)一行完成，因為右邊全部先求值。 -
Q: 手續費在買入時扣和賣出時扣有差嗎？ A: 結果一樣。在買入時扣：
hold = cash - price - fee，賣出時：cash = hold + price。無論放在哪一側，每次完整交易（買+賣）都恰好扣一次 fee。選賣出時扣比較直觀。
理解測驗
🤔 為什麼 hold 的初始值是 -prices[0] 而不是 0？
🤔 手續費 fee 為什麼只在賣出時扣除？