无锡市网站建设_网站建设公司_在线商城_seo优化

哈喽各位，我是前端小L。

欢迎来到贪心算法专题第七篇！

题目很简单：给你一个整数数组 nums 和一个整数 k。你必须执行 k 次取反操作（可以选择同一个下标）。最后，让数组的总和最大。

直觉告诉我们：

1. 负数是宝藏：把负数变成正数，总和会蹭蹭往上涨。

2. 绝对值越大越好：把-100变成100，比把-1变成1划算多了。

3. 正数是累赘：如果负数都变完了，k还没用完，我们不得不把正数变回负数。这时候要选最小的正数，因为-1总比-100造成的损失小。

力扣 1005. K 次取反后最大化数组和

https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/

题目分析：

• 输入：nums数组，k次操作。

• 目标：最大数组和。

• 规则：必须操作 K 次。

例子：nums = [2, -3, -1, 5, -4],k = 2

• 第一次：肯定选-4（绝对值最大），变成4。数组：[2, -3, -1, 5, 4]。

• 第二次：肯定选-3（剩下里绝对值最大的），变成3。数组：[2, 3, -1, 5, 4]。

• 结果：2+3-1+5+4 = 13。

核心思维：两次贪心

我们可以把这个过程分为两个阶段：

1. 第一阶段贪心（处理负数）：

   • 策略：优先把绝对值最大的负数变成正数。

   • 这就要求我们按绝对值大小对数组进行排序。

   • 例如[-4, -3, -1, 2, 5]（按绝对值降序是5, -4, -3, 2, -1，或者我们直接处理负数逻辑）。

2. 第二阶段贪心（处理多余的 K）：

   • 如果负数都变完了，k还是正数（且是奇数）。

   • 策略：找一个当前数值最小的元素进行取反。

   • 因为这时候数组全是正数（或0），取反一定会减少总和。为了让总和减少得最少，必须选最小的那个数。

算法流程

为了完美配合这两种贪心策略，我们可以使用一个巧妙的排序方法：按绝对值从大到小排序。

1. 排序：将数组按照绝对值从大到小排序。

   • 原数组：[2, -3, -1, 5, -4]

   • 排序后：[5, -4, -3, 2, -1](绝对值：5, 4, 3, 2, 1)

2. 第一轮遍历：

   • 从头往后走。如果遇到负数且k > 0，就把它变正，k--。

   • 此时数组变为：[5, 4, 3, 2, -1](-4和-3变了)。

   • 此时k可能还有剩余。

3. 第二轮处理：

   • 如果k此时是偶数，不需要操作（对同一个数取反两次等于没变）。

   • 如果k是奇数，必须再操作一次。

   • 因为我们是按绝对值从大到小排序的，所以数组的最后一个元素，一定是绝对值最小的（也就是数值最小的非负数）。

   • 直接对nums[n-1]取反。

4. 求和。

代码实现 (C++)

C++

#include <vector> #include <algorithm> // for sort, abs #include <numeric> // for accumulate using namespace std; class Solution { // 自定义比较函数：按绝对值从大到小排序 static bool cmp(int a, int b) { return abs(a) > abs(b); } public: int largestSumAfterKNegations(vector<int>& nums, int k) { // 1. 按绝对值从大到小排序 sort(nums.begin(), nums.end(), cmp); // 2. 第一步贪心：把绝对值大的负数变成正数 for (int i = 0; i < nums.size(); i++) { if (nums[i] < 0 && k > 0) { nums[i] *= -1; k--; } } // 3. 第二步贪心：如果 k 还没用完（且是奇数） // 此时数组里全是正数（或者0），且最后一个元素绝对值最小 if (k % 2 == 1) { nums[nums.size() - 1] *= -1; } // 4. 求和 int sum = 0; for (int num : nums) { sum += num; } return sum; } };

深度辨析：为什么要按绝对值排序？

如果我们只按普通升序排序[-4, -3, -1, 2, 5]：

• 处理完负数后，数组变成[4, 3, 1, 2, 5]。

• 如果此时k剩 1，我们需要找最小的数。

• 在普通排序后的数组里，最小的数1在中间位置，找起来比较麻烦（需要再次遍历或排序）。

而按绝对值降序排序[5, -4, -3, 2, -1]：

• 处理完后变成[5, 4, 3, 2, -1]（假设 -1 没被翻，或者翻了变成 1）。

• 无论如何，绝对值最小的那个数，永远在数组的末尾。

• 这让第二步处理变得只有 $O(1)$ 的复杂度。

深度复杂度分析

• 时间复杂度：O(N log N)

  • 主要消耗在排序上。

  • 遍历和求和都是 $O(N)$。

• 空间复杂度：O(1)

  • 如果是 C++ 的sort，通常需要 $O(\log N)$ 的栈空间，但不需要额外数组。

总结：贪心的“优先级”

这道题教会了我们如何建立贪心优先级：

1. 最高优先级：消除“大负数”（收益最大）。

2. 次高优先级：消除“小负数”。

3. 最低优先级（迫不得已）：牺牲“小正数”（损失最小）。

通过排序，我们将这些优先级线性化，从而一趟扫描解决问题。

下一题预告：加油站

接下来我们要挑战贪心算法中最经典、也最容易让人懵圈的题目——“加油站”。

• 你有一个油箱无限大的车，想绕环形公路跑一圈。

• 每个加油站有油gas[i]，去下一站消耗cost[i]。

• 你需要找一个起点，保证能跑完一圈。

贪心策略非常神奇：如果你尝试从 A 跑到 B，发现油不够了，那么A 和 B 之间的所有站点都不可能作为起点。为什么？

准备好发车了吗？下期见！