LeetCode 1005. K 次取反后最大化的数组和

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节跳动
标签
数组 排序 贪心
目录

题目描述

✅ 1005. K 次取反后最大化的数组和

题意分析

给一个整数数组和次数 k，每次必须挑一个下标把它的值取相反数，恰好操作 k 次（同一个下标可以被反复挑中），问操作完之后数组和最大是多少。

有两个字眼决定了整道题的形态。第一是「恰好 k 次」而不是「至多 k 次」：次数用不完也得用，不能提前收手，这就逼出了「把多余次数消耗在同一个元素上」的想法——同一个数取反两次等于没动，所以真正起作用的只是剩余次数的奇偶性。第二是「同一下标可重复选」：如果限定每个下标最多选一次，问题会复杂得多；允许重复反而给了消耗多余次数的出口。

从收益角度看，把一个负数 x 取反，和会增加 -2x > 0；把一个非负数 y 取反，和会减少 2y ≥ 0。所以次数应当优先花在负数上，而且越「负」的数收益越大——这提示要按值排序，而不是按绝对值或原顺序处理。

约束是 nums.length ≤ 10^4、k ≤ 10^4、元素绝对值不超过 100，规模很小，$O(n \log n)$ 的排序完全够用，不必追求线性。

边界有三处：负数个数可能多于 k（次数不够，只能挑最负的几个翻）；负数个数可能少于 k（次数有剩，要看奇偶）；数组里可能有 0，一旦有 0，多余的偶数次和奇数次操作都可以白白倒在 0 上，不产生任何损失。

解法：排序 + 贪心

核心思路

一次取反会让数组和改变 -2x：当 x < 0 时收益为正，而且 x 越小，收益越大；当 x >= 0 时只会造成损失。因此先升序排序，按从小到大的顺序翻转负数，就是按收益从大到小使用操作次数。

这个选择可以用交换论证说明：若某个方案翻了负数 b，却没有翻更小的负数 a（a < b < 0），把对 b 的取反换到 a 上，操作次数不变，而数组和额外增加 2(b-a) > 0。所以最优方案一定优先翻最小的负数。

所有能翻的负数处理完后，剩余操作只看奇偶性：同一元素连续取反两次，数组不变。若剩余次数为偶数，可以全部抵消；若为奇数，必须让一个元素最终多取反一次，此时选择绝对值最小的元素，损失 2 * minAbs 最小。数组中有 0 时，minAbs = 0，多余操作不会造成损失。

不变量：扫描排序后的负数前缀时，已使用的操作始终取得当前可获得的最大总增益；负数阶段结束后，尚未使用的操作只可能带来 0 或一次最小损失。 这两个阶段合在一起得到全局最优解。

解题步骤

  1. 将数组升序排序，使负数按绝对值从大到小排列在前缀。
  2. 从左向右扫描；只要当前数为负且 k > 0，就将它取反并令 k--。
  3. 扫描修改后的数组，同时计算总和 sum 和最小绝对值 minAbs。
  4. 若剩余 k 为奇数，返回 sum - 2 * minAbs；否则直接返回 sum。

例如 nums = [-8, 3, -5, -3, -5, -2]、k = 6。排序后依次翻正五个负数，得到 [8, 5, 5, 3, 2, 3]，绝对值之和为 26，还剩一次操作。最小绝对值是 2，因此答案为 26 - 2 * 2 = 22。

若操作次数先用完，例如 [-4, -3, -2]、k = 2，只翻前两个数后 k = 0，直接求和得到 5；不能为了消除剩余负数而超用操作。

代码实现

import java.util.Arrays;

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);

        for (int i = 0; i < nums.length && nums[i] < 0 && k > 0; i++) {
            nums[i] = -nums[i];
            k--;
        }

        int sum = 0;
        int minAbs = Math.abs(nums[0]);
        for (int num : nums) {
            sum += num;
            minAbs = Math.min(minAbs, Math.abs(num));
        }
        return (k & 1) == 0 ? sum : sum - 2 * minAbs;
    }
}

import "sort"

func largestSumAfterKNegations(nums []int, k int) int {
	sort.Ints(nums)

	for i := 0; i < len(nums) && nums[i] < 0 && k > 0; i++ {
		nums[i] = -nums[i]
		k--
	}

	sum := 0
	minAbs := nums[0]
	if minAbs < 0 {
		minAbs = -minAbs
	}
	for _, v := range nums {
		sum += v
		abs := v
		if abs < 0 {
			abs = -abs
		}
		if abs < minAbs {
			minAbs = abs
		}
	}
	if k%2 == 1 {
		sum -= 2 * minAbs
	}
	return sum
}

复杂度分析

  • 时间复杂度： $O(n log n)$，排序占主导；翻负数和统计答案各为 $O(n)$。
  • 空间复杂度： 除排序实现所需的调用栈外为 $O(1)$；Java 和 Go 的标准库排序通常还需要 $O(log n)$ 级别的栈空间。算法会原地修改输入数组。

关键点总结

  • 取反负数的收益是 -2x，因此应优先处理值最小的负数，而不是最接近 0 的负数。
  • “同一位置可重复操作”把剩余次数化成了奇偶问题：偶数次抵消，奇数次只需承担一次最小损失。
  • 最小绝对值必须在负数翻转后计算；被翻正的元素也可能成为新的最小值。
  • 正确性由两部分组成：负数阶段的交换论证，以及剩余阶段对最小损失的选择。

易错点总结

  • 剩余奇数次时直接翻排序后的 nums[0]： [-8, -5, 2] 翻完负数后数组是 [8, 5, 2]，此时应翻 2，而不是原下标 0 的 8。
  • 不判断正负就连续翻前 k 个元素： [1, 2, 3]、k = 2 的最优结果仍是 6，两次操作应在同一元素上抵消。
  • 忽略剩余次数的奇偶性： [2, 3]、k = 1 必须损失 4，答案是 1；k = 2 则可以抵消，答案是 5。
  • 按原顺序遇到负数就翻： [3, -1, -7]、k = 1 若先翻 -1 得到 -3，翻 -7 才能得到最优值 9。
  • 漏掉 0 的作用： 只要当前数组含 0，任意剩余次数都可以作用在 0 上，最小损失为 0。

相似题目

题目 难度 考察点
1029. 两地调度 中等 同样是排序后取前缀的贪心，但排序键是两种选择的差值而非原值，且名额固定为一半
455. 分发饼干 简单 两个数组各自排序后双指针匹配，贪心对象是「配对」而不是「取反」
881. 救生艇 中等 排序后头尾双指针，每步的局部决策要同时看最轻和最重两端
976. 三角形的最大周长 简单 降序排序后取第一组合法的相邻三元组，贪心依据是三角不等式而非收益大小
628. 三个数的最大乘积 简单 同样要考虑负数与符号，答案在「最大三个」与「最小两个配最大一个」之间取较大者
561. 数组拆分 简单 排序后取所有偶数下标求和，最优性同样靠交换论证证明
870. 优势洗牌 中等 双方都排序后做田忌赛马式匹配，打不过的用最弱的去消耗，贪心结构更复杂