ARTICLE DETAIL

资讯详情

深耕郑州网站建设与运营推广的一线实战洞察。

元宝 LeetCode 152. 乘积最大子数组 Rust实现

元宝    LeetCode 152. 乘积最大子数组 Rust实现 下面是 LeetCode 152 乘积最大子数组 的 Rust 实现思路与 Python 版完全一致我给你提供 LeetCode 标准写法 和 完整可运行示例。✅ 核心思路简要回顾由于乘积会遇到负数符号翻转和零重置同时维护“imax”以当前元素结尾的最大乘积和“imin”最小乘积遇到负数时交换“imax” 和“imin”每一步都允许从当前元素重新开始“max(x, imax * x)”用“ans” 记录全局最大值✅ 解法一LeetCode 风格推荐impl Solution {pub fn max_product(nums: Vec) - i32 {let mut imax nums[0];let mut imin nums[0];let mut ans nums[0];for i in 1..nums.len() { let x nums[i]; // 遇到负数最大最小会反转先交换 if x 0 { std::mem::swap(mut imax, mut imin); } // 更新以当前位置结尾的最大/最小乘积 imax i32::max(x, imax * x); imin i32::min(x, imin * x); // 更新全局答案 ans i32::max(ans, imax); } ans }}✅ 解法二更简洁的写法使用元组交换pub fn max_product(nums: Vec) - i32 {let (mut imax, mut imin, mut ans) (nums[0], nums[0], nums[0]);for x in nums[1..] { if x 0 { (imax, imin) (imin, imax); } imax imax * x.max(x); // 注意这里应该是 i32::max(x, imax * x) imin imin * x.min(x); // 同上用 i32::min ans ans.max(imax); } ans}⚠️ 上面写法二的“imax * x.max(x)” 是伪代码风格正确写法是“i32::max(x, imax * x)”我修正如下pub fn max_product_clean(nums: Vec) - i32 {let (mut imax, mut imin, mut ans) (nums[0], nums[0], nums[0]);for x in nums[1..] { if x 0 { (imax, imin) (imin, imax); } imax i32::max(x, imax * x); imin i32::min(x, imin * x); ans i32::max(ans, imax); } ans}✅ 完整可运行测试代码fn max_product(nums: Vec) - i32 {let (mut imax, mut imin, mut ans) (nums[0], nums[0], nums[0]);for i in 1..nums.len() { let x nums[i]; if x 0 { std::mem::swap(mut imax, mut imin); } imax i32::max(x, imax * x); imin i32::min(x, imin * x); ans i32::max(ans, imax); } ans}fn main() {let test_cases vec![vec![2, 3, -2, 4], // 6vec![-2, 0, -1], // 0vec![-2, 3, -4], // 24vec![-1], // -1vec![0, 2, 0, 3, 4], // 12vec![-4, -3, -2], // 12];for nums in test_cases { let result max_product(nums.clone()); println!(输入: {:?} - 输出: {}, nums, result); }}输出输入: [2, 3, -2, 4] - 输出: 6输入: [-2, 0, -1] - 输出: 0输入: [-2, 3, -4] - 输出: 24输入: [-1] - 输出: -1输入: [0, 2, 0, 3, 4] - 输出: 12输入: [-4, -3, -2] - 输出: 12 复杂度分析指标 数值时间复杂度 O(n) — 单次遍历空间复杂度 O(1) — 仅用常数变量 Rust 实现要点交换变量Rust 不允许直接“a, b b, a” 像 Python 那样但可以用“(a, b) (b, a)” 元组解构或“std::mem::swap(mut a, mut b)”整数溢出LeetCode 测试用例在“i32” 范围内实际工程中如果可能溢出可以用“i64” 中间变量“i32::max” /“i32::min”Rust 标准库提供的关联函数等价于 Python 的“max()” /“min()”需要我补充前缀积/后缀积解法或处理溢出的安全版本吗
返回列表