LeetCode 3695. 交换元素后的最大交替和 — Rust 实现核心思路这道题的关键在于通过 swaps 连通的下标属于同一个连通块块内元素可以任意排列。1. 并查集分组将 swaps 中的每对下标进行合并得到若干连通块。2. 统计奇偶下标每个连通块内统计原始数组中属于该块的奇数下标个数 odd则偶数下标个数为 sz - odd。3. 贪心分配对每个连通块内的所有元素降序排序把最大的 sz - odd 个元素分配到偶数下标贡献 剩下的 odd 个最小的分配到奇数下标贡献 -。时间复杂度 O(n log n)空间复杂度 O(n)。Rust 代码rustuse std::collections::HashMap;struct UnionFind {parent: Vecusize,// 每个根节点记录该连通块中奇数下标的个数odd_count: Vecusize,}impl UnionFind {fn new(n: usize) - Self {let mut odd_count vec![0; n];for i in 0..n {odd_count[i] i 1; // 奇数下标为1偶数下标为0}UnionFind {parent: (0..n).collect(),odd_count,}}fn find(mut self, x: usize) - usize {if self.parent[x] ! x {self.parent[x] self.find(self.parent[x]);}self.parent[x]}fn union(mut self, x: usize, y: usize) {let px self.find(x);let py self.find(y);if px ! py {self.parent[px] py;self.odd_count[py] self.odd_count[px];}}}impl Solution {pub fn max_alternating_sum(nums: Veci32, swaps: VecVeci32) - i64 {let n nums.len();let mut uf UnionFind::new(n);// 1. 构建并查集for swap in swaps {let p swap[0] as usize;let q swap[1] as usize;uf.union(p, q);}// 2. 按连通块收集元素let mut groups: HashMapusize, Veci64 HashMap::new();for i in 0..n {let root uf.find(i);groups.entry(root).or_default().push(nums[i] as i64);}let mut ans: i64 0;// 3. 对每个连通块贪心分配for (root, mut vals) in groups {let odd uf.odd_count[root]; // 该连通块中奇数下标个数let sz vals.len();let even sz - odd; // 偶数下标个数// 降序排序大的放偶数下标()小的放奇数下标(-)vals.sort_unstable_by(|a, b| b.cmp(a));for i in 0..even {ans vals[i];}for i in even..sz {ans - vals[i];}}ans}}关键点说明要点 说明并查集维护 odd_count 合并时累加两个连通块的奇数下标数量保证后续能直接知道每个块需要多少个减号位置HashMap 分组 root 作为 key收集该连通块内所有可交换的元素值降序排序后分段 前 even 个元素贡献 后 odd 个元素贡献 -这是使交替和最大的最优策略返回 i64 nums[i] 最大为 10^9n 最大为 10^5总和可能溢出 i32必须用 i64