Medium

题目描述

给你一个整数数组 nums。你可以按任意顺序重新排列元素。

数组 arr 的交替得分定义为：

score = arr[0]² - arr[1]² + arr[2]² - arr[3]² + ...

返回重新排列 nums 元素后可能的最大交替得分。

示例 1：

输入：nums = [1,2,3]
输出：12
解释：
nums 的一种可能重排是 [2,1,3]，它在所有可能的重排中给出最大交替得分。
交替得分计算如下：
score = 2² - 1² + 3² = 4 - 1 + 9 = 12

示例 2：

输入：nums = [1,-1,2,-2,3,-3]
输出：16
解释：
nums 的一种可能重排是 [-3,-1,-2,1,3,2]，它在所有可能的重排中给出最大交替得分。
交替得分计算如下：
score = (-3)² - (-1)² + (-2)² - (1)² + (3)² - (2)² = 9 - 1 + 4 - 1 + 9 - 4 = 16

约束条件：

  • 1 <= nums.length <= 10⁵
  • -4 * 10⁴ <= nums[i] <= 4 * 10⁴

提示：

  • 得分使用值的平方。nums 的原始符号不影响平方项。
  • 在交替和中，偶数索引贡献正值，奇数索引贡献负值。

解题思路

解题思路

这道题的关键洞察是：由于使用的是平方值，所以原数的符号不影响结果，我们只需要考虑绝对值。

核心思路：

  1. 由于平方运算，负数和正数的平方值相同，因此我们只需关注数组中每个元素的绝对值
  2. 在交替和公式中，偶数位置的元素贡献正值（+），奇数位置的元素贡献负值（-）
  3. 为了最大化结果，我们希望：
    • 偶数位置放置绝对值较大的数
    • 奇数位置放置绝对值较小的数

贪心策略： 将所有元素按绝对值排序，然后按照"大小大小…“的模式排列：

  • 绝对值最大的放在位置0（+贡献）
  • 绝对值最小的放在位置1（-贡献）
  • 绝对值第二大的放在位置2（+贡献）
  • 绝对值第二小的放在位置3（-贡献）
  • …

具体实现时，我们可以直接对绝对值排序，然后模拟这个放置过程计算最终得分。

推荐解法： 排序 + 贪心策略

代码实现

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        vector<int> absNums;
        for (int num : nums) {
            absNums.push_back(abs(num));
        }
        sort(absNums.begin(), absNums.end());
        
        long long result = 0;
        int n = nums.size();
        int left = 0, right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                result += (long long)absNums[right] * absNums[right];
                right--;
            } else {
                result -= (long long)absNums[left] * absNums[left];
                left++;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        abs_nums = [abs(num) for num in nums]
        abs_nums.sort()
        
        result = 0
        n = len(nums)
        left, right = 0, n - 1
        
        for i in range(n):
            if i % 2 == 0:
                result += abs_nums[right] ** 2
                right -= 1
            else:
                result -= abs_nums[left] ** 2
                left += 1
        
        return result

public class Solution {
    public long MaxAlternatingSum(int[] nums) {
        int[] absNums = new int[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            absNums[i] = Math.Abs(nums[i]);
        }
        Array.Sort(absNums);
        
        long result = 0;
        int n = nums.Length;
        int left = 0, right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                result += (long)absNums[right] * absNums[right];
                right--;
            } else {
                result -= (long)absNums[left] * absNums[left];
                left++;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAlternatingSum = function(nums) {
    const squares = nums.map(x => x * x).sort((a, b) => b - a);
    let score = 0;
    
    for (let i = 0; i < squares.length; i++) {
        if (i % 2 === 0) {
            score += squares[i];
        } else {
            score -= squares[i];
        }
    }
    
    return score;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序操作上
空间复杂度O(n)需要额外数组存储绝对值