DeepSeek LeetCode 3256. 放三个车的价值之和最大 I Rust实现

对于 LeetCode 3256 题“放三个车的价值之和最大 I”核心逻辑是三辆车不能在同一行或同一列且数据规模 (m, n ≤ 100) 下无法直接枚举所有组合。 核心解法题目要求三个车占据的三个行和三个列互不相同。关键推导出每一行只需考虑该行价值最大的三个格子因为其他格子被最优解替代后价值会更高。因此总枚举次数可控在 \binom{m}{3} \times 3! 量级十分高效。 Rust 代码实现rustimpl Solution {pub fn maximum_value_sum(board: VecVeci32) - i64 {let m board.len();let n board[0].len();// 存储每一行最大的三个值及列索引let mut top vec![vec![(0, 0); 3]; m];// 预处理每一行最大的三个值for i in 0..m {let mut row_vals (0..n).map(|j| (board[i][j], j)).collect::Vec_();row_vals.sort_unstable_by_key(|(val, _)| -val);for k in 0..3 {if k row_vals.len() {top[i][k] row_vals[k];} else {top[i][k] (i32::MIN, 0);}}}let mut ans i64::MIN;// 枚举三行的索引组合 (r1, r2, r3)for r1 in 0..m {for k1 in 0..3 {let (val1, c1) top[r1][k1];if val1 i32::MIN { continue; }let val1 val1 as i64;for r2 in r11..m {for k2 in 0..3 {let (val2, c2) top[r2][k2];if val2 i32::MIN { continue; }if c2 c1 { continue; }let val2 val2 as i64;for r3 in r21..m {for k3 in 0..3 {let (val3, c3) top[r3][k3];if val3 i32::MIN { continue; }if c3 c1 || c3 c2 { continue; }let val3 val3 as i64;ans ans.max(val1 val2 val3);}}}}}}ans}} 代码步骤详解1. 预处理核心候选值遍历 board对每一行的格子按价值降序排序保留前三个最大价值及其列索引存储到 top 数组。2. 高效三重循环枚举· r1 r2 r3 保证行号不重复。· c1, c2, c3 互不相同则列号不重复。· 计算三个候选值的和 val1 val2 val3 并更新全局最大值 ans。3. 鲁棒性处理谨慎处理可能不足三列的行以及最小值 i32::MIN。该解法通过巧妙的预处理和枚举在 Rust 中实现了高效且符合题意的解答。