LeetCode 3480. 删除一个冲突对后最大子数组数目 — Rust 实现rustimpl Solution {pub fn max_subarrays(n: i32, conflicting_pairs: VecVeci32) - i64 {let n n as usize;// groups[a] 存储所有以 a 为左端点a b的冲突对的 b 值let mut groups: VecVecusize vec![Vec::new(); n 1];for pair in conflicting_pairs {let mut a pair[0] as usize;let mut b pair[1] as usize;if a b {std::mem::swap(mut a, mut b);}groups[a].push(b);}let mut ans: i64 0; // 不删除任何冲突对时的合法子数组数量let mut extra: Veci64 vec![0; n 2]; // extra[b0] 表示删除导致最小值为 b0 的冲突对后的额外贡献let mut max_extra: i64 0;let mut b0 n 1; // 当前最小 blet mut b1 n 1; // 当前次小 b// 倒序枚举左端点for a in (1..n).rev() {for b in groups[a] {if b b0 {b1 b0;b0 b;} else if b b1 {b1 b;}}// 左端点为 a 时的基础贡献合法右端点范围 [a, b0-1]ans (b0 - a) as i64;// 如果删除使得 b0 变成 b1 的冲突对额外贡献为 b1 - b0if b0 n {extra[b0] (b1 - b0) as i64;if extra[b0] max_extra {max_extra extra[b0];}}}ans max_extra}}---核心思路步骤 说明预处理 对每个冲突对 (a, b) 保证 a b将 b 存入 groups[a]倒序枚举 (1..n).rev() 枚举左端点 a此时所有 x ≥ a 的冲突对都已入队维护双最值 b0最小右端点、b1次小右端点基础贡献 左端点为 a 时合法右端点范围 [a, b0-1]贡献 b0 - a删除贡献 若删除导致 b0 的冲突对最小值升为 b1额外增加 b1 - b0累加取最大 同个 b0 可能对应多个左端点的额外贡献用 extra[b0] 累加后取全局最大时间复杂度O(n m)m 为冲突对数量空间复杂度O(n m)Rust 注意事项- 全程使用 usize 作为数组索引仅在累加答案时转换为 i64- std::mem::swap 用于交换 a 和 b 保证 a b- extra 数组大小设为 n 2 以避免 b0 n 1 时的越界访问虽然实际只在 b0 n 时写入