3695. 使用交换最大化交替和

Hard

题目描述

给你一个整数数组 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]

解题思路

这道题的关键是理解通过交换操作，我们可以在连通分量内任意重排元素。因此需要使用并查集来找到所有连通分量。

核心思路：

构建连通分量：使用并查集处理交换对，将能够互相交换的索引归为同一连通分量
贪心策略：对于每个连通分量，我们需要让较大的值放在偶数位置（系数为+1），较小的值放在奇数位置（系数为-1）
计算贡献：设连通分量中有E个偶数位置，则应将最大的E个值放在偶数位置，剩余值放在奇数位置

数学分析： 对于一个连通分量，设其包含的值为 v1, v2, …, vk（降序排列），其中有E个偶数位置。

最大的E个值放在偶数位置，贡献为 +v1 + v2 + … + vE
剩余值放在奇数位置，贡献为 -(vE+1 + vE+2 + … + vk)
总贡献 = 2×(前E个值的和) - (所有值的和)

这个公式的推导：前E个值在偶数位置贡献+值，在总和中被减去一次，所以净贡献是2倍；后面的值在奇数位置贡献-值，已经在总和中了。

算法步骤：

用并查集构建连通分量
对每个连通分量收集其包含的值和偶数位置数量
对每个分量的值排序，应用贪心策略计算最大贡献
累加所有分量的贡献得到最终答案

代码实现

class Solution {
public:
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            parent[x] = y;
        }
    }
    
    long long maxAlternatingSum(vector<int>& nums, vector<vector<int>>& swaps) {
        int n = nums.size();
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // Build connected components
        for (auto& swap : swaps) {
            unite(swap[0], swap[1]);
        }
        
        // Group indices by component
        unordered_map<int, vector<int>> components;
        for (int i = 0; i < n; i++) {
            components[find(i)].push_back(i);
        }
        
        long long result = 0;
        
        for (auto& [root, indices] : components) {
            // Collect values and count even positions
            vector<long long> values;
            int evenCount = 0;
            
            for (int idx : indices) {
                values.push_back(nums[idx]);
                if (idx % 2 == 0) {
                    evenCount++;
                }
            }
            
            // Sort values in descending order
            sort(values.rbegin(), values.rend());
            
            long long sumAll = 0;
            long long sumTopE = 0;
            
            for (int i = 0; i < values.size(); i++) {
                sumAll += values[i];
                if (i < evenCount) {
                    sumTopE += values[i];
                }
            }
            
            // Component contribution: 2 * sumTopE - sumAll
            result += 2 * sumTopE - sumAll;
        }
        
        return result;
    }
};

class Solution:
    def maxAlternatingSum(self, nums: List[int], swaps: List[List[int]]) -> int:
        n = len(nums)
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        # Build connected components
        for p, q in swaps:
            unite(p, q)
        
        # Group indices by component
        components = {}
        for i in range(n):
            root = find(i)
            if root not in components:
                components[root] = []
            components[root].append(i)
        
        result = 0
        
        for indices in components.values():
            # Collect values and count even positions
            values = [nums[idx] for idx in indices]
            even_count = sum(1 for idx in indices if idx % 2 == 0)
            
            # Sort values in descending order
            values.sort(reverse=True)
            
            sum_all = sum(values)
            sum_top_e = sum(values[:even_count])
            
            # Component contribution: 2 * sumTopE - sumAll
            result += 2 * sum_top_e - sum_all
        
        return result

public class Solution {
    private int[] parent;
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    private void Unite(int x, int y) {
        int px = Find(x);
        int py = Find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
    
    public long MaxAlternatingSum(int[] nums, int[][] swaps) {
        int n = nums.Length;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // Build connected components
        foreach (var swap in swaps) {
            Unite(swap[0], swap[1]);
        }
        
        // Group indices by component
        var components = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            int root = Find(i);
            if (!components.ContainsKey(root)) {
                components[root] = new List<int>();
            }
            components[root].Add(i);
        }
        
        long result = 0;
        
        foreach (var indices in components.Values) {
            // Collect values and count even positions
            var values = new List<long>();
            int evenCount = 0;
            
            foreach (int idx in indices) {
                values.Add(nums[idx]);
                if (idx % 2 == 0) {
                    evenCount++;
                }
            }
            
            // Sort values in descending order
            values.Sort((a, b) => b.CompareTo(a));
            
            long sumAll = values.Sum();
            long sumTopE = values.Take(evenCount).Sum();
            
            // Component contribution: 2 * sumTopE - sumAll
            result += 2 * sumTopE - sumAll;
        }
        
        return result;
    }
}

var maxAlternatingSum = function(nums, swaps) {
    const n = nums.length;
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function union(x, y) {
        const px = find(x);
        const py = find(y);
        if (px !== py) {
            parent[px] = py;
        }
    }
    
    for (const [p, q] of swaps) {
        union(p, q);
    }
    
    const components = new Map();
    for (let i = 0; i < n; i++) {
        const root = find(i);
        if (!components.has(root)) {
            components.set(root, []);
        }
        components.get(root).push(i);
    }
    
    let result = 0;
    
    for (const indices of components.values()) {
        const values = indices.map(i => nums[i]).sort((a, b) => b - a);
        const positions = indices.slice().sort((a, b) => a - b);
        
        let componentSum = 0;
        for (let i = 0; i < positions.length; i++) {
            const pos = positions[i];
            const sign = pos % 2 === 0 ? 1 : -1;
            componentSum += sign * values[i];
        }
        
        result += componentSum;
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(n log n + m α(n))
空间复杂度	O(n)

其中 n 是数组长度，m 是交换对数量，α(n) 是阿克曼函数的反函数。时间复杂度主要由排序决定，并查集操作的时间复杂度可以认为是常数。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析