目录
贪心算法简介
此篇是贪心算法的第一部分，后面应该还有二三四部分，都是七八道题一部分。
定义：贪心算法（又称贪婪算法）是指，在对于问题求解时总是能做出在当前看来是最好的选择，也就是说，不是从整体最优上加以考虑，他所指出的是在某种意义上的局部最优解。
贪心选择是所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。
当一个问题的最优解包含其子问题的最优解时，称此问题提具有最优子结构性质，运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。贪心算法的每一次操作都对结果产生影响。贪心算法的每一次操作都对结果产生直接影响，贪心算法对每个子问体的解决方案都做出选择，不能回退。
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。
贪心算法一般的过程
- 建立数学模型来描述问题。
- 将求解的问题分为若干个子问题。
- 将每一子问题求解，得到子问题的局部最优解。
- 将子问题的局部最优解合成原来解问题的一个解。
贪心算法的成功取决于问题是否具有“最优子结构”和“贪婪选择属性”，如果问题具有这两个属性，那么贪心算法可能找到全局最优解，否则，它可能只能找到近似最优解或不可行解。贪心算法的应用包括图论问题（如最短路径问题）、优化问题（如背包问题）等。
①力扣860. 柠檬水找零
难度 简单
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
1 <= bills.length <= 10^5bills[i]不是5就是10或是20
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
}
};解析代码
贪心策略：分情况讨论：
- 遇到 5 元钱，直接收下。
- 遇到 10 元钱，找零 5 元钱之后，收下。
- 遇到 20 元钱：先尝试凑 10 + 5 的组合。如果凑不出来，拼凑 5 + 5 + 5 的组合。（因为5的价值比较大（可以找10也可以找20，10只能找20，所以把5保留，这就体现贪心））
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for(int i = 0; i < bills.size(); ++i)
{
if(bills[i] == 5)
++five;
else if(bills[i] == 10)
{
if(five == 0)
return false;
--five;
++ten;
}
else // 20块，找15，先看有没有10
{
if(five != 0 && ten != 0) // 贪心
--five, --ten;
else if(five >= 3)
five -= 3;
else
return false;
}
}
return true;
}
};
②力扣2208. 将数组和减半的最少操作次数
难度 中等
给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
示例 1：
输入：nums = [5,19,8,1] 输出：3 解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。 以下是将数组和减少至少一半的一种方法： 选择数字 19 并减小为 9.5 。 选择数字 9.5 并减小为 4.75 。 选择数字 8 并减小为 4 。 最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。 nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。 我们需要 3 个操作实现题目要求，所以返回 3 。 可以证明，无法通过少于 3 个操作使数组和减少至少一半。
示例 2：
输入：nums = [3,8,20] 输出：3 解释：初始 nums 的和为 3 + 8 + 20 = 31 。 以下是将数组和减少至少一半的一种方法： 选择数字 20 并减小为 10 。 选择数字 10 并减小为 5 。 选择数字 3 并减小为 1.5 。 最终数组为 [1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。 nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31/2 = 15.5 。 我们需要 3 个操作实现题目要求，所以返回 3 。 可以证明，无法通过少于 3 个操作使数组和减少至少一半。
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^7
class Solution {
public:
int halveArray(vector<int>& nums) {
}
};解析代码
贪心策略：每次挑选出当前数组中最大的数，然后减半直到数组和减少到至少一半为止。
为了快速挑选出数组中最大的数，可以利用堆这个数据结构。
class Solution {
public:
int halveArray(vector<int>& nums) {
int ret = 0;
double sum = 0, target = 0;
priority_queue<double> q(nums.begin(), nums.end());
for(auto& e : nums)
{
sum += e;
}
target = sum / 2;
while(target < sum)
{
double tmp = q.top() / 2;
q.pop();
q.push(tmp);
sum -= tmp;
++ret;
}
return ret;
}
};
③力扣179. 最大数
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2] 输出："210"
示例 2：
输入：nums = [3,30,34,5,9] 输出："9534330"
提示：
1 <= nums.length <= 1000 <= nums[i] <= 10^9
class Solution {
public:
string largestNumber(vector<int>& nums) {
}
};解析代码1_仿函数
贪心策略：按照题目的要求，重新定义一个新的排序规则，然后排序即可。
排序规则：
- 「A 拼接 B」 大于 「B 拼接 A」，那么 A 在前，B 在后。
- 「A 拼接 B」 等于 「B 拼接 A」，那么 A B 的顺序可以任意。
- 「A 拼接 B」 小于 「B 拼接 A」，那么 B 在前，A 在后。
class Solution {
struct cmp
{
bool operator()(int a, int b)
{
string str1 = to_string(a);
string str2 = to_string(b);
return str1 + str2 > str2 + str1;
}
};
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), cmp());
string ret;
for(auto& e : nums)
{
ret += to_string(e);
}
return ret[0] == '0' ? "0" : ret; // 去掉前导0
}
};解析代码2_Lambda
贪心策略在上面讲了，用Lambda简化下代码：
class Solution {
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int a, int b)
{
string str1 = to_string(a);
string str2 = to_string(b);
return str1 + str2 > str2 + str1;
}
);
string ret;
for(auto& e : nums)
{
ret += to_string(e);
}
return ret[0] == '0' ? "0" : ret; // 去掉前导0
}
};
④力扣376. 摆动序列
难度 中等
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。- 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7 解释：这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9] 输出：2
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
}
};解析代码
贪心策略：对于某一个位置来说：
- 如果接下来呈现上升趋势的话，让其上升到波峰的位置。（极大值）
- 如果接下来呈现下降趋势的话，让其下降到波谷的位置。（极小值）
因此，如果把整个数组放在折线图中，统计出所有的波峰以及波谷的个数即可。（极值）
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int ret = 1, left = 0, n = nums.size(); // left是左边的增长趋势
for(int i = 0; i < n - 1; ++i)
{
int right = nums[i + 1] - nums[i]; // 用到i+1，所以上面遍历到n-1
if(right == 0)
continue; // 跳过中间相同的点
if(left * right <= 0) // 加等号是第一次。left等于0且后面还有不同元素的情况
++ret;
left = right;
}
return ret;
}
};
⑤力扣300. 最长递增子序列
难度 中等
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
提示：
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
}
};解析代码
这道题是很经典的一道题，已经用爆搜和DP写过了，看看贪心的写法：
贪心策略：
我们在考虑最长递增子序列的长度的时候，其实并不关心这个序列长什么样子，我们只是关心最后一个元素是谁。这样新来一个元素之后，我们就可以判断是否可以拼接到它的后面。
因此，可以创建一个数组，统计长度为 x 的递增子序列中，最后一个元素是谁。为了尽可能的让这个序列更长（贪心），我们仅需统计长度为 x 的所有递增序列中最后一个元素的最小值。
统计的过程中发现，数组中的数呈现递增趋势，因此可以使用二分来查找插入位置。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> arr; // 大小代表最长长度，值代表这个长度的子序列的最后一个值
arr.push_back(nums[0]);
for(int i = 1; i < nums.size(); ++i)
{
if(nums[i] > arr.back())
{
arr.push_back(nums[i]);
}
else // 二分找到要放的位置（找大于等于nums[i]的左端点）
{
int left = 0, right = arr.size() - 1;
while(left < right)
{
int mid = (right + left) >> 1; // 元素个数是偶数时，中点是中间的左边
if(arr[mid] < nums[i])
left = mid + 1;
else // (arr[mid] >= nums[i])
right = mid; // 自己可能是左端点
}
arr[left] = nums[i];
}
}
return arr.size();
}
};
⑥力扣334. 递增的三元子序列
难度 中等
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5] 输出：true 解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1] 输出：false 解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6] 输出：true 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示：
1 <= nums.length <= 5 * 10^5-2^31 <= nums[i] <= 2^31 - 1
进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
}
};解析代码
贪心策略： 力扣300. 最长递增子序列的简化版。 不用一个数组存数据，仅需两个变量即可。也不用二分插入位置，仅需两次比较就可以找到插如位置。
class Solution {
public:
int increasingTriplet(vector<int>& nums) {
int a = nums[0], b = INT_MAX;
for(int i = 1; i < nums.size(); ++i)
{
if(nums[i] > b)
return true;
else if(nums[i] > a)
b = nums[i];
else // 小于a
a = nums[i];
}
return false;
}
};
⑦力扣674. 最长连续递增序列
难度 简单
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2] 输出：1 解释：最长连续递增序列是 [2], 长度为1。
提示：
1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
}
};解析代码
贪心策略： （贪心 + 双指针）找到以某个位置为起点的最长连续递增序列之后（设这个序列的末尾为 right 位置），接下来直接以 right + 1 的位置为起点寻找下一个最长连续递增序列。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int left = 0, ret = 0, sz = nums.size();
while(left < sz)
{
int right = left + 1; // 找到递增区间的末端
while(right < sz && nums[right] > nums[right - 1])
{
++right;
}
ret = max(ret, right - left);
left = right; // 贪心：直接在循环中更新下⼀个位置的起点
}
return ret;
}
};
本篇完。
下一篇是DFS爆搜深搜回溯剪枝类型的OJ。
下下篇是贪心算法的第二部分，七八道题贪心题。
![Amazon云计算AWS之[5]关系数据库服务RDS](https://img-blog.csdnimg.cn/direct/4e277b72fd4640198032f2462dc9eecf.png)
