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

(贪心) LeetCode 1005. K 次取反后最大化的数组和

news 2025/11/22 12:59:02

原题链接

一. 题目描述

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组可能的最大和。

示例 1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

提示：

1 <= nums.length <= 104
-100 <= nums[i] <= 100
1 <= k <= 104

二. 解题思路

本题的意思也十分简单，给你一个数组以及一个整数k，需要你在数组中选择一些元素将他们置反，前提是只能操作k 次，但是可以选择同一元素多次操作。

（1）聪明的小伙伴已经猜到了，只要我每次将最小的一个数选择置反，然后操作k 次，就可以得到最大的和了。没错，这种做法完全正确，我们直接使用优先队列小根堆来存储数组元素，然后每次取出堆头元素置反再添加回去，这样k 次即可。

（2）我们再来看看再原数组中如何操作，细心的同学可以发现，我们只需要在有限的k 次操作中将绝对值大的负数置反，这样就能使得最终结果尽可能的大一些，如果在将所有负数置反之后发现k 任有剩余，那么我们只需要选择一个最小的元素操作k 次就可以了，这样就能使得答案最大，那么我们怎么操作数组呢，难不成每操作一个元素就排序一次吗？这样的做法还不如使用优先队列呢，其实不然，我们只需要在排序的时候做一些操作即可，按照数组中数的绝对值从大到小排序即可，例如(1，5， 2， -8，-4， k = 5)，这样排序之后就可以得到（-8，5，-4，2，1，k = 5）；然后我们只需要从头遍历数组，优先处理负数，在k 次范围内将绝对值最大的负数置反即可，遍历结束之后，如果k 任有剩余，只需要将数组末尾的元素(排序之后末尾的就是最小的)执行k 次操作即可，有些同学想要使用while（k--）来操作，然后反复将最后一位元素进行置反，完全没必要，如果剩余的k 是偶数的话，就不用管了，因为在k 次操作之后值是不会变的，如果是奇数，只需要将值 *-1 即可。

最后遍历优先队列或者数组将总和求出返回即可。

话不多说！！！上代码！！

三. 代码

1. 使用优先队列：

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<>> que;for(int i = 0; i < nums.size(); i++){que.push(nums[i]);}while(k--){int node = que.top(); que.pop();que.push(-node);}int res = 0;while(!que.empty()){int node = que.top(); que.pop();res += node;}return res;}
};

2. 在原数组中操作：

class Solution {
public:static bool com(int a, int b){return abs(a) > abs(b);}int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), com);for(int i = 0 ; i< nums.size(); i++){if(nums[i] < 0 && k > 0){nums[i] *= -1;k--;}}if(k % 2 == 1) nums[nums.size() - 1] *= -1; int res = 0;for(int i = 0; i < nums.size(); i++){res += nums[i];}return res;}
};