买卖股票的最佳时机全系列核心推演
专题核心思想
股票买卖系列是动态规划中“状态机模型”的经典代表。其本质是将每一天的决策抽象为若干相互转换的状态（如“持有股票”、“不持有股票”、“处于冷冻期”等），进而写出清晰的状态转移方程，并利用滚动变量实现 的空间压缩。
一、LeetCode 121. 买卖股票的最佳时机（一次交易）
1. 核心思路
只允许买入一次并卖出一次。遍历价格数组，维护历史最低买入成本 buy；每天如果卖出，潜在收益为 price - buy，更新全局最大利润 maxProfit 即可。
2. 代码实现
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let minPrice = prices[0];
let max = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
max = Math.max(max, prices[i] - minPrice);
}
}
return max;
};- 时间复杂度：
- 空间复杂度：
二、LeetCode 122. 买卖股票的最佳时机 II（无限次交易）
1. 核心思路
可以进行无限次买卖，但同一时刻最多只能持有一支股票。
- 贪心视角：由于交易无手续费，每一段跨天上涨（）的差价都可以拆解为单日的正收益累加；
- 数学等价：只要 ，就纳入总收益。
2. 代码实现
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
const diff = prices[i] - prices[i - 1];
if (diff > 0) {
profit += diff;
}
}
return profit;
};- 时间复杂度：
- 空间复杂度：
三、LeetCode 309. 买卖股票的最佳时机含冷冻期
LeetCode 309. Best Time to Buy and Sell Stock with Cooldown · 难度：中等
1. 核心思路（三状态机）
卖出股票后次日无法买入（1 天冷冻期）。定义第 天结束时的 3 种互斥状态：
dp[0]：当前持有股票时的最大收益；dp[1]：当前不持有股票且处于冷冻期（即今天刚卖出）；dp[2]：当前不持有股票且不在冷冻期（可以随时买入）。
状态转移方程：
2. 代码实现
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
if (prices.length <= 1) return 0;
// 初始状态：持有 / 刚卖出(冷冻) / 自由状态
let [hold, cooldown, free] = [-prices[0], 0, 0];
for (let i = 1; i < prices.length; i++) {
const cur = prices[i];
const newHold = Math.max(hold, free - cur);
const newCooldown = hold + cur;
const newFree = Math.max(free, cooldown);
hold = newHold;
cooldown = newCooldown;
free = newFree;
}
return Math.max(cooldown, free);
};- 时间复杂度：
- 空间复杂度：
四、LeetCode 714. 买卖股票的最佳时机含手续费
LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee · 难度：中等
1. 核心思路
每笔交易都需要支付一笔固定手续费 fee。
定义状态：
hold：持有股票的最大收益；cash：未持有股票的最大收益（在卖出时扣除手续费）。
转移方程：
2. 代码实现
/**
* @param {number[]} prices
* @param {number} fee
* @return {number}
*/
var maxProfit = function(prices, fee) {
let hold = -prices[0];
let cash = 0;
for (let i = 1; i < prices.length; i++) {
cash = Math.max(cash, hold + prices[i] - fee);
hold = Math.max(hold, cash - prices[i]);
}
return cash;
};- 时间复杂度：
- 空间复杂度：
五、LeetCode 123. 买卖股票的最佳时机 III（最多两次交易）
1. 核心思路（四状态推导）
任意一天结束时，至多经历 4 个关键节点：
buy1：第一次买入后持有的最大收益；sell1：第一次卖出后不持有的最大收益；buy2：第二次买入后持有的最大收益；sell2：第二次卖出后不持有的最大收益。
2. 代码实现
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let buy1 = -prices[0];
let sell1 = 0;
let buy2 = -prices[0];
let sell2 = 0;
for (let i = 1; i < prices.length; i++) {
const cur = prices[i];
buy1 = Math.max(buy1, -cur);
sell1 = Math.max(sell1, buy1 + cur);
buy2 = Math.max(buy2, sell1 - cur);
sell2 = Math.max(sell2, buy2 + cur);
}
return sell2;
};- 时间复杂度：
- 空间复杂度：
六、LeetCode 188. 买卖股票的最佳时机 IV（最多 k 次交易）
1. 核心思路
当 时，等价于无限次交易（LeetCode 122）。 当 时，维护大小为 的数组：
buy[j]：第 次买入后的最大收益；sell[j]：第 次卖出后的最大收益。
转移方程：
2. 代码实现
/**
* @param {number} k
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(k, prices) {
const len = prices.length;
if (len <= 1 || k === 0) return 0;
// 退化为无限次交易
if (k >= Math.floor(len / 2)) {
let profit = 0;
for (let i = 1; i < len; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
const buy = new Array(k + 1).fill(-Infinity);
const sell = new Array(k + 1).fill(0);
buy[0] = -prices[0];
for (let i = 0; i < len; i++) {
const p = prices[i];
buy[0] = Math.max(buy[0], -p);
for (let j = 1; j <= k; j++) {
buy[j] = Math.max(buy[j], sell[j - 1] - p);
sell[j] = Math.max(sell[j], buy[j] + p);
}
}
return Math.max(...sell);
};- 时间复杂度：
- 空间复杂度：