DeepSeek LeetCode 122. 买卖股票的最佳时机 II Rust实现

LeetCode 122. 买卖股票的最佳时机 II（Rust 实现）

思路

由于可以无限次交易，且任意时刻最多持有一股，所以只要后一天价格比前一天高，就可以在前一天买入、后一天卖出，赚取差价。将所有相邻两天的正收益累加即为最大利润。

也可以用动态规划：维护两个状态——不持股的最大利润 cash 和持股的最大利润 hold。

Rust 实现（贪心法）

implSolution{pubfnmax_profit(prices:Vec<i32>)->i32{letmutprofit=0;foriin1..prices.len(){ifprices[i]>prices[i-1]{profit+=prices[i]-prices[i-1];}}profit}}

Rust 实现（动态规划）

implSolution{pubfnmax_profit(prices:Vec<i32>)->i32{ifprices.is_empty(){return0;}// cash: 不持股的最大利润，hold: 持股的最大利润letmutcash=0;letmuthold=-prices[0];foriin1..prices.len(){letnew_cash=cash.max(hold+prices[i]);letnew_hold=hold.max(cash-prices[i]);cash=new_cash;hold=new_hold;}cash}}

关键点

1. 贪心法：每一段上涨都拆成每天的正收益，累加即可，时间复杂度 O(n)，空间 O(1)。
2. 动态规划：
   · cash 表示当天不持股的最大利润，hold 表示当天持股的最大利润。
   · 状态转移：
   · cash = max(cash, hold + prices[i])（今天卖出）
   · hold = max(hold, cash - prices[i])（今天买入，注意这里用的是前一天的 cash，因为当天只能操作一次，但代码中先计算 new_cash 再计算 new_hold，使用旧 cash 是正确的）
   · 最终返回 cash。
3. Rust 注意：使用 i32::max 或 .max() 方法；prices 为空时直接返回 0。

复杂度

· 时间：O(n)，遍历一次。
· 空间：O(1)，只用了常数个变量。

测试用例

#[test]fntest_max_profit(){assert_eq!(Solution::max_profit(vec![7,1,5,3,6,4]),7);assert_eq!(Solution::max_profit(vec![1,2,3,4,5]),4);assert_eq!(Solution::max_profit(vec![7,6,4,3,1]),0);}