1. 算法介绍
贪心算法（Greedy Algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解，但未必是全局最优解。
贪心算法一般分为四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
使用贪心算法时。可以通过数学归纳法等方式来证明局部最优解就是全局最优解（比较麻烦）。或者通过举反例说明贪心算法不成立，若没有想到反例就可以先尝试贪心算法。若贪心算法得到的结果不对，说明局部最优解不一定是全局最优解，这时候可以再考虑使用动态规划。
2. 题目分析
2.1 分发饼干
原题链接：455. 分发饼干
题目说明：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
题目分析：对于每一次分饼干来说，最优选择是先分配尽可能小的饼干。为了能够满足孩子胃口，所以也需要从胃口最小的孩子开始尝试。若该饼干能够满足胃口最小的孩子，就可以分出去了。若满足不了，那么更不能满足其他胃口更大的孩子了。这种情况就扔掉该饼干继续分下一块，直到所有饼干用完。
核心代码：
int findContentChildren(vector<int>& g, vector<int>& s) {
int res = 0, i = 0, j = 0;
// 将孩子胃口和饼干大小全部按升序排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());
while (i < g.size() && j < s.size()) {
// 若饼干能满足孩子，则分配该饼干
if (s[j] >= g[i]) {
++i;
++j;
++res;
} else {
// 若该饼干满足不了当前胃口最小的孩子，则一定满足不了其他孩子
// 放弃该饼干
++j;
}
}
return res;
}2.2 跳跃游戏
原题链接：55. 跳跃游戏
题目说明：给定一个非负整数数组 nums ，你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
题目分析：因为数组中的每个元素代表可以跳跃的最大长度，所以在最大长度之前的所有位置都可以到达。因此每次跳跃可以选择跳到使下一次能够到达的距离最远的点。最后再判断一下能够到达的最大范围是否包括了终点，即可得出最后结论。
核心代码：
bool canJump(vector<int>& nums) {
if (nums.size() < 2)
return true;
// 能够到达的最远范围
int maxLen = 0;
for (int i = 0; i < nums.size() - 1; ) {
// 记录能够到达的最远范围
maxLen = max(maxLen, i + nums[i]);
++i;
// 该位置已经无法到达了，则后续所有位置都无法到达
if (i > maxLen)
return false;
}
return true;
}2.3 跳跃游戏 II
原题链接：跳跃游戏 II
题目说明：给定一个非负整数数组 nums ，最初位于数组的第一个位置，数组中的每个元素代表在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设总是可以到达数组的最后一个位置。
题目分析：该题与上题类似，但是需要记录跳跃的次数。
核心代码：
int jump(vector<int>& nums) {
if (nums.size() < 2)
return 0;
int step = 0;
int curMax = nums[0];
int nextMax = 0;
for (int i = 0; i < nums.size(); ++i) {
// 跳跃范围包含终点，则只需要再跳一步即可
if (curMax >= nums.size() - 1)
return step + 1;
// 统计跳完下一步后所能到达的最大范围
nextMax = max(nextMax, i + nums[i]);
// 已遍历完当前范围，选择上面统计出来的能得到的范围最大的点进行跳跃
if (i == curMax) {
curMax = nextMax;
nextMax = 0;
++step;
}
}
// 若能到达终点，则一定在上述循环中返回了
return -1;
}2.4 K次取反后最大化的数组和
原题链接：1005. K 次取反后最大化的数组和
题目说明：给定一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。重复这个过程恰好 k 次。可以多次选择同一个下标 i 。修改完成后，返回数组可能的最大和。
题目分析：对于每一次修改来说，优先把较大的负数变成正数。若数组里均为非负数且还需进行调整，则优先选择较小的非负数（包括0），这样对总和的影响最小。
核心代码：
// 自己写的sort的排序规则，此处踩了个大坑
// abs(m) >= abs(n)这里 >= 不能换成 >
// 否则可能出现溢出异常
// 在写比较规则时，对于相同的两个数一定要返回 false
// 参考资料：https://blog.csdn.net/jiange_zh/article/details/78240806
bool myCmp(int m, int n) {
return abs(m) >= abs(n) ? false : true;
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
if (nums.empty())
return 0;
// 按绝对值大小升序排序
sort(nums.begin(), nums.end(), myCmp);
for (int i = nums.size() - 1; i >= 0; --i) {
// 若调整次数用完
if (k <= 0)
break;
// 从后往前调整所有的负数
if (nums[i] < 0) {
nums[i] = -nums[i];
--k;
}
}
// 负负得正，若最后还剩偶数次调整则互相抵消
// 剩奇数次调整的话讲第一个数取相反数
if ((k & 0x1) == 1)
nums[0] = -nums[0];
// 求和
int sum = 0;
for (int &num : nums)
sum += num;
return sum;
}2.5 买卖股票的最佳时机 II
原题链接：122. 买卖股票的最佳时机 II
题目说明：给定一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和出售股票。你在任何时候最多只能持有一股股票。也可以先购买，然后在同一天出售。计算能获得的最大利润。
题目分析：对于相邻两天来说，只要能赚钱便可以先买入再卖出。若不能赚钱，则不进行买入卖出操作。最终总利润为所有能够赚到的子利润只和。
核心代码：
int maxProfit(vector<int>& prices) {
if (prices.size() == 1)
return 0;
int res = 0;
for (int i = 0; i < prices.size() - 1; i++)
{
// 若相邻两天价格之差为正，则买入卖出可以赚钱，进行该操作
// 将本次买入卖出操作的利润加到总利润里
res += (prices[i+1] - prices[i] > 0 ? prices[i+1] - prices[i] : 0);
}
return res;
}2.6 分发糖果
原题链接：135. 分发糖果
题目说明： n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
- 请你给每个孩子分发糖果，计算需要准备的最少糖果数目。
题目分析：题目中的 “相邻两个孩子评分更高的孩子会获得更多的糖果” 条件可以拆成两个，即
- 当右边的学生评分比左边高时，右边的学生糖果更多；（左规则）
- 当左边的学生评分比右边高时，左边的学生糖果更多；（右规则）
将上述两条规则分别称为左规则和右规则，则分配糖果时必须同时满足上述两种规则。因此可以遍历两次，分别求出只满足左规则情况下的分配方式和仅满足右规则情况下的分配方式，然后每个学生的糖果数量就是这两种分配方式中的较大值。
核心代码：
int candy(vector<int>& ratings) {
// 先全部分配1个糖果
vector<int> left(ratings.size(), 1);
vector<int> right(ratings.size(), 1);
// 按左规则分配
for (int i = 0; i < ratings.size() - 1; ++i) {
if (ratings[i + 1] > ratings[i])
left[i + 1] = left[i] + 1;
}
// 按右规则分配
for (int i = ratings.size() - 1; i >= 1; --i) {
if (ratings[i - 1] > ratings[i])
right[i - 1] = right[i] + 1;
}
int res = 0;
// 综合左规则与右规则，取较大值
for (int i = 0; i < ratings.size(); ++i) {
res += max(left[i], right[i]);
}
return res;
}