当前位置：首页 > news >正文

LeetCode 3695. 交换元素后的最大交替和【无向图连通分量,快速选择】困难

news 2026/7/11 20:29:04

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个整数数组nums。

你希望最大化nums的交替和：将偶数下标的元素相加并减去奇数索引的元素获得的值。即nums[0] - nums[1] + nums[2] - nums[3]...

同时给你一个二维整数数组swaps，其中swaps[i] = [pi, qi]。对于swaps中的每对[pi, qi]，你可以交换索引pi和qi处的元素。这些交换可以进行任意次数和任意顺序。

返回nums可能的最大交替和。

示例 1:

输入：nums=[1,2,3],swaps=[[0,2],[1,2]]输出：4

解释：当nums为[2, 1, 3]或[3, 1, 2]时，可以实现最大交替和。例如，你可以通过以下方式得到nums = [2, 1, 3]。

交换nums[0]和nums[2]。此时nums为[3, 2, 1]。
交换nums[1]和nums[2]。此时nums为[3, 1, 2]。
交换nums[0]和nums[2]。此时nums为[2, 1, 3]。

示例 2:

输入：nums=[1,2,3],swaps=[[1,2]]输出：2

解释：不进行任何交换即可实现最大交替和。

示例 3:

输入：nums=[1,1000000000,1,1000000000,1,1000000000],swaps=[]输出：-2999999997

解释：由于我们不能进行任何交换，因此不进行任何交换即可实现最大交替和。

提示:

2 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= swaps.length <= 10^5
swaps[i] = [pi, qi]
0 <= pi < qi <= nums.length - 1
[pi, qi] != [pj, qj]

方法建图+DFS/并查集

用并查集将p i p_ipi和q i q_iqi合并。合并后，同一集合（连通块）中的元素可以随意交换。

贪心地：

交替和中取负号的元素，，我们把较小元素交换到奇数下标上。
交替和中取正号的元素，位于偶数下标，我们把较大元素交换到偶数下标上。

为此，并查集需要额外维护集合中的奇数下标个数。

对于同一组，设奇数下标个数为o d d oddodd。把元素从小到大排序后，前o d d oddodd个元素取负号，其余元素取正号。

// 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/classUnionFind{privatefinalint[]fa;// 代表元publicfinalint[]odd;// 集合中的奇数个数UnionFind(intn){// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己fa=newint[n];odd=newint[n];for(inti=0;i<n;i++){fa[i]=i;odd[i]=i%2;}}// 返回 x 所在集合的代表元// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元publicintfind(intx){// 如果 fa[x] == x，则表示 x 是代表元if(fa[x]!=x){fa[x]=find(fa[x]);// fa 改成代表元}returnfa[x];}// 把 from 所在集合合并到 to 所在集合中publicvoidmerge(intfrom,intto){intx=find(from);inty=find(to);if(x==y){// from 和 to 在同一个集合，不做合并return;}fa[x]=y;// 合并集合odd[y]+=odd[x];// 更新集合中的奇数个数}}classSolution{publiclongmaxAlternatingSum(int[]nums,int[][]swaps){intn=nums.length;UnionFinduf=newUnionFind(n);for(int[]p:swaps){uf.merge(p[0],p[1]);}List<Integer>[]g=newArrayList[n];Arrays.setAll(g,_->newArrayList<>());for(inti=0;i<n;i++){g[uf.find(i)].add(nums[i]);// 相同集合的元素分到同一组}longans=0;for(inti=0;i<n;i++){List<Integer>a=g[i];if(a.isEmpty()){continue;}Collections.sort(a);intodd=uf.odd[i];// 小的取负号，大的取正号for(intj=0;j<a.size();j++){intx=a.get(j);ans+=j<odd?-x:x;}}returnans;}}

// 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/classUnionFind{vector<int>fa;// 代表元public:vector<int>odd;// 集合中的奇数个数UnionFind(intn):fa(n),odd(n){// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己for(inti=0;i<n;i++){fa[i]=i;odd[i]=i%2;}}// 返回 x 所在集合的代表元// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元intfind(intx){// 如果 fa[x] == x，则表示 x 是代表元if(fa[x]!=x){fa[x]=find(fa[x]);// fa 改成代表元}returnfa[x];}// 把 from 所在集合合并到 to 所在集合中// 返回是否合并成功voidmerge(intfrom,intto){intx=find(from),y=find(to);if(x==y){// from 和 to 在同一个集合，不做合并return;}fa[x]=y;// 合并集合。修改后就可以认为 from 和 to 在同一个集合了odd[y]+=odd[x];// 更新集合中的奇数个数}};classSolution{public:longlongmaxAlternatingSum(vector<int>&nums,vector<vector<int>>&swaps){intn=nums.size();UnionFinduf(n);// 假设并查集已实现for(auto&p:swaps){uf.merge(p[0],p[1]);}vector<vector<int>>g(n);for(inti=0;i<n;i++){g[uf.find(i)].push_back(nums[i]);// 相同集合的元素分到同一组}longlongans=0;for(inti=0;i<n;i++){auto&a=g[i];if(a.empty()){continue;}ranges::sort(a);// 或快速选择：ranges::nth_element(a, a.begin() + odd);intodd=uf.odd[i];// 小的取负号，大的取正号ans-=reduce(a.begin(),a.begin()+odd,0LL);ans+=reduce(a.begin()+odd,a.end(),0LL);}returnans;}};

# 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/classUnionFind:def__init__(self,n:int):# 一开始有 n 个集合 {0}, {1}, ..., {n-1}# 集合 i 的代表元是自己self._fa=list(range(n))# 代表元self.odd=[i%2foriinrange(n)]# 集合中的奇数个数self.cc=n# 连通块个数# 返回 x 所在集合的代表元# 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元deffind(self,x:int)->int:# 如果 fa[x] == x，则表示 x 是代表元fa=self._faiffa[x]!=x:fa[x]=self.find(fa[x])# fa 改成代表元returnfa[x]# 把 from 所在集合合并到 to 所在集合中defmerge(self,from_:int,to:int)->None:x,y=self.find(from_),self.find(to)ifx==y:# from 和 to 在同一个集合，不做合并returnself._fa[x]=y# 合并集合self.odd[y]+=self.odd[x]# 更新集合中的奇数个数classSolution:defmaxAlternatingSum(self,nums:List[int],swaps:List[List[int]])->int:uf=UnionFind(len(nums))forp,qinswaps:uf.merge(p,q)g=defaultdict(list)fori,xinenumerate(nums):g[uf.find(i)].append(x)# 相同集合的元素分到同一组ans=0fori,aing.items():a.sort()odd=uf.odd[i]# 小的取负号，大的取正号ans+=sum(a[odd:])-sum(a[:odd])returnans

// 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/typeunionFindstruct{fa[]int// 代表元odd[]int// 集合中的奇数个数}funcnewUnionFind(nint)unionFind{fa:=make([]int,n)odd:=make([]int,n)// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己fori:=rangefa{fa[i]=i odd[i]=i%2}returnunionFind{fa,odd}}// 返回 x 所在集合的代表元// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元func(u unionFind)find(xint)int{// 如果 fa[x] == x，则表示 x 是代表元ifu.fa[x]!=x{u.fa[x]=u.find(u.fa[x])// fa 改成代表元}returnu.fa[x]}// 把 from 所在集合合并到 to 所在集合中func(u*unionFind)merge(from,toint){x,y:=u.find(from),u.find(to)ifx==y{// from 和 to 在同一个集合，不做合并return}u.fa[x]=y// 合并集合u.odd[y]+=u.odd[x]// 更新集合中的奇数个数}funcmaxAlternatingSum(nums[]int,swaps[][]int)(ansint64){n:=len(nums)uf:=newUnionFind(n)for_,p:=rangeswaps{uf.merge(p[0],p[1])}g:=make([][]int,n)fori,x:=rangenums{f:=uf.find(i)g[f]=append(g[f],x)// 相同集合的元素分到同一组}fori,a:=rangeg{ifa==nil{continue}slices.Sort(a)odd:=uf.odd[i]// 小的取负号，大的取正号forj,x:=rangea{ifj<odd{ans-=int64(x)}else{ans+=int64(x)}}}return}

复杂度分析：

时间复杂度：O ( n log ⁡ n ) O(n\log n)O(nlogn)或O ( n ) O(n)O(n)，其中n nn是n u m s numsnums的长度。使用快速选择算法求出前k kk小元素，可将时间复杂度优化到O ( n ) O(n)O(n)。
空间复杂度：O ( n ) O(n)O(n)。