LeetCode 122. 买卖股票的最佳时机 IIRust 实现思路由于可以无限次交易且任意时刻最多持有一股所以只要后一天价格比前一天高就可以在前一天买入、后一天卖出赚取差价。将所有相邻两天的正收益累加即为最大利润。也可以用动态规划维护两个状态——不持股的最大利润 cash 和持股的最大利润 hold。Rust 实现贪心法implSolution{pubfnmax_profit(prices:Veci32)-i32{letmutprofit0;foriin1..prices.len(){ifprices[i]prices[i-1]{profitprices[i]-prices[i-1];}}profit}}Rust 实现动态规划implSolution{pubfnmax_profit(prices:Veci32)-i32{ifprices.is_empty(){return0;}// cash: 不持股的最大利润hold: 持股的最大利润letmutcash0;letmuthold-prices[0];foriin1..prices.len(){letnew_cashcash.max(holdprices[i]);letnew_holdhold.max(cash-prices[i]);cashnew_cash;holdnew_hold;}cash}}关键点贪心法每一段上涨都拆成每天的正收益累加即可时间复杂度 O(n)空间 O(1)。动态规划· cash 表示当天不持股的最大利润hold 表示当天持股的最大利润。· 状态转移· cash max(cash, hold prices[i])今天卖出· hold max(hold, cash - prices[i])今天买入注意这里用的是前一天的 cash因为当天只能操作一次但代码中先计算 new_cash 再计算 new_hold使用旧 cash 是正确的· 最终返回 cash。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);}