贪心算法实战：取反最大化、环形加油站与糖果分发
1. K次取反后数组和的最大化
给定整数数组 nums 与整数 k，允许对任意元素执行 k 次取反操作（可重复选择同一位置）。目标是使最终数组的总和最大。
核心策略：优先对绝对值最大的负数进行取反，以提升整体和。若所有负数处理完毕后仍有剩余操作次数：
- 若剩余次数为偶数，可将同一元素反复取反，最终仍为正数，不影响结果。
- 若剩余次数为奇数，则应将最小的正数取反，以最小化损失。
实现思路：按元素绝对值从大到小排序，遍历数组，对负数进行取反并减少操作次数；累加总和。最后根据剩余操作次数的奇偶性调整结果。
class Solution {
public:
static bool compare(int a, int b) {
return abs(a) > abs(b);
}
int maximumSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), compare);
int total = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] < 0 && k > 0) {
nums[i] = -nums[i];
--k;
}
total += nums[i];
}
// 若剩余操作次数为奇数，需将最小正值取反
if (k % 2 == 1) {
total -= 2 * nums[nums.size() - 1];
}
return total;
}
};
2. 环形加油站问题
在环形路径上有 n 个加油站，每个站提供 gas[i] 升油，前往下一站需消耗 cost[i] 升油。汽车油箱容量无限，初始无油。求是否存在起点可绕行一圈。
关键观察：若总油量不小于总消耗，则存在解；否则无法完成。
贪心策略：维护当前累积油量 currentFuel，从索引 0 开始累加每段净油量（gas[i] - cost[i]）。一旦累积值为负，说明当前起点不可行，重置起点为下一位，并清空累计值。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int currentFuel = 0;
int totalFuel = 0;
int startIdx = 0;
for (int i = 0; i < gas.size(); ++i) {
int net = gas[i] - cost[i];
currentFuel += net;
totalFuel += net;
if (currentFuel < 0) {
currentFuel = 0;
startIdx = i + 1;
}
}
return totalFuel < 0 ? -1 : startIdx;
}
};
3. 最少糖果分配
有 n 个孩子排成一列，每个孩子有一个评分 ratings[i]。要求：
- 每人至少一个糖果。
- 相邻中评分更高的孩子必须获得更多糖果。
求满足条件的最少糖果总数。
解法：使用双遍扫描法：
- 从左到右：若当前孩子评分高于前一个，则其糖果数 = 前一个 + 1。
- 从右到左：若当前孩子评分高于后一个，更新其糖果数为
max(后一个+1, 当前值)，确保两边约束都满足。
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candies(ratings.size(), 1);
// 左向扫描：保证递增关系
for (int i = 1; i < ratings.size(); ++i) {
if (ratings[i] > ratings[i-1]) {
candies[i] = candies[i-1] + 1;
}
}
// 右向扫描：保证递减关系
for (int i = ratings.size() - 2; i >= 0; --i) {
if (ratings[i] > ratings[i+1]) {
candies[i] = max(candies[i], candies[i+1] + 1);
}
}
return accumulate(candies.begin(), candies.end(), 0);
}
};
