前言
大家好，我是jiantaoyab，这篇文章将给大家介绍贪心算法和贪心算法题目的练习和解析，贪心算法的本质就是每一个阶段都是局部最优，从而实现全局最优。我们在做题的同时，不仅要把题目做出来，还要有严格的证明。
柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为
5美元。顾客排队购买你的产品，（按账单bills支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付
5美元、10美元或20美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付5美元。注意，一开始你手头没有任何零钱。
题目分析
如果顾客给5块钱，就收下。
如果顾客给10块钱，查找有没有5块钱，没有return false，有找5块钱
如果顾客给20块钱，此时有2种策略。
- 给顾客找10块钱和5块钱
- 给顾客找3张5块钱
在这道题目中5块钱的作用是很大的，假如我给顾客3张5块钱，那我剩下的5块钱就少了很多，当遇到下一个顾客可能不能找零，此时生意就做不成了。
我们用交换论证法证明一下
代码
class Solution {
public:
bool lemonadeChange(vector<int>& bills)
{
int five = 0, ten = 0;
for(auto x : bills)
{
if(x == 5) five++;
else if(x == 10)
{
if(five == 0) return false;
five--; ten++;
}
else
{
if(ten && five)
{
ten--;five--;
}
else if(five >= 3)
{
five -= 3;
}
else return false;
}
}
return true;
}
};
将数组和减半的最少操作次数
给你一个正整数数组
nums。每一次操作中，你可以从nums中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
题目分析
这个题目还是很好理解的，只要我们每次选出数组中最大的数减半，直到数组和减少到一半就是结果了。
选出最大的元素可以用大根堆。
用交换论证法证明，当完全遍历一次，就能得到结果了。
代码
class Solution {
public:
int halveArray(vector<int>& nums) {
priority_queue<double> heap;
double sum = 0.0;
int count = 0;
for(auto x : nums)
{
heap.push(x);
sum += x;
}
sum /= 2;
while(sum > 0)
{
double tmp = heap.top();
heap.pop();
tmp /= 2.0;
sum -= tmp;
heap.push(tmp);
count++;
}
return count;
}
};
最大数
给定一组非负整数
nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。**注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。
题目分析
题目要求返回组成的最大整数，那就要求大的数要放到前面，假设有2个数a，b，那么有3种情况。
ab > ba 此时 a 放到 b 的前面
ab =ba 此时 a和 b 谁放到前面都可以
ab < ba 此时 a放到 b 的前面
这么看这个过程，和排序的过程不是一样的吗？我们知道a>b，b>c,是能推出a>c的？那么在这道题中怎么证明能推出这个结论呢？
我们先来看看全序关系，全序关系用 “<=”表述 , 满足全序关系的有3个特点。
- 反对称性：如果a≤b且b≤a，则a=b。
- 传递性：如果a≤b且b≤c，则a≤c。
- 完全性：对于集合中的任意两个元素，它们之间要么可以比较，要么其中一个元素大于另一个元素。
可以看到我们要证明出全序关系就行。
证明完全性：
ab 和 ba 我们看出一个数，那他们之间是能比较大小的，能比较大小就有可能存在一个元素大于另一个元素。
证明反对称性：ab <= ba ab >= ba ==> ab =ba
假设 a代表x位，b代表y位，那么ab 改写成 a* 10^y + b，b * 10^x + a;
a* 10^y + b 我举个例子，假如a= 100，b=20，那么ab = 10020，想要拼接是不是先得在100后面补2个0那就是b的位数。
带入上面的式子得
1
：
a
∗
1
0
y
+
b
<
=
b
∗
1
0
x
+
a
1：a* 10^y + b <= b * 10^x + a
1：a∗10y+b<=b∗10x+a
2 ： a ∗ 1 0 y + b > = b ∗ 1 0 x + a 2：a* 10^y + b >= b * 10^x + a 2：a∗10y+b>=b∗10x+a
3 ： a ∗ 1 0 y + b = = b ∗ 1 0 x + a 3：a* 10^y + b == b * 10^x + a 3：a∗10y+b==b∗10x+a
用夹逼定理
a
∗
1
0
y
+
b
<
=
b
∗
1
0
x
+
a
<
=
a
∗
1
0
y
+
b
a* 10^y + b <= b * 10^x + a <=a*10^y+b
a∗10y+b<=b∗10x+a<=a∗10y+b
所以
a
∗
1
0
y
+
b
=
=
b
∗
1
0
x
+
a
a* 10^y + b == b * 10^x + a
a∗10y+b==b∗10x+a
最后证明传递性：
对于任意的 a，b，c， ab>=ba 且 bc<=cb ==> ac > ca;
假设 a代表x位，b代表y位，c代表z位。具体的改写和上面同理
特殊情况，a = b = c = 0 的话，还是套上面的公式，在本题中0 是可以当做一位数的
a
∗
1
0
y
+
b
>
=
b
∗
1
0
x
+
a
a* 10^y + b >= b * 10^x + a
a∗10y+b>=b∗10x+a
通过移项，改写成；
a
∗
(
1
0
y
−
a
)
>
=
(
1
0
x
−
b
)
∗
b
a*(10^y -a) >= (10^x - b)*b
a∗(10y−a)>=(10x−b)∗b
同样的，将剩下的2个式子也改写
b
∗
(
1
0
z
−
1
)
>
=
(
1
0
y
−
1
)
∗
c
b*(10^z -1) >= (10^y - 1)*c
b∗(10z−1)>=(10y−1)∗c
a ∗ ( 1 0 z − 1 ) > = ( 1 0 x − 1 ) ∗ c a*(10^z -1) >= (10^x - 1)*c a∗(10z−1)>=(10x−1)∗c
可以看到最后的式子是没有b的，我们把b消去就行，我们现在讨论的是a，b，c至少都是有1位数的情况，本题0也能当成一位数，所以能当成分母除。
(
1
0
y
−
1
/
1
0
x
−
1
)
∗
a
>
=
b
(10^y-1/10^x-1)*a >=b
(10y−1/10x−1)∗a>=b
b > = ( 1 0 y − 1 / 1 0 z − 1 ) ∗ c b>=(10^y-1/10^z-1)*c b>=(10y−1/10z−1)∗c
通过上面2个式子的化简移项，最后得出
a
∗
(
1
0
z
−
1
)
>
=
(
1
0
x
−
1
)
∗
c
a*(10^z -1) >= (10^x - 1)*c
a∗(10z−1)>=(10x−1)∗c
所以是满足全序关系的，所以我们这个题目是能排序的。
代码
class Solution {
public:
string largestNumber(vector<int>& nums) {
//将数字转化为字符串
vector<string> tmp;
for(auto x : nums) tmp.push_back(to_string(x));
//排序
sort(tmp.begin(), tmp.end(),[](const string& s1, const string& s2)
{
return s1 + s2 > s2 + s1;
});
//返回结果
string ret;
for(auto s : tmp) ret += s;
if(ret[0] == '0') return "0";
return ret;
}
};
摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 **摆动序列 。**第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。- 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组
nums，返回nums中作为 摆动序列 的 最长子序列的长度 。
题目分析
可以看出题目要求求最长的摆动的子序列，把数列在坐标系中用点的形式画出来，然后连成折线。
用反证法证明
图像是连续的，所以上面所说的波峰和波谷在数学上称作极值点。
下面图片在贪心解中一个有4个极值点，假如最优解在这个情况下，能选更多的点，那它一定比4个极值点更多。
代码
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if(n < 2) return n;
int ret = 0, left_trend = 0;
for(int i = 0; i < n - 1; i++)
{
int right_trend = nums[i + 1] - nums[i];
if(right_trend == 0) continue; //平台直接跳过
// <= 0 把起点也上
if(right_trend * left_trend <= 0) ret++; //波峰或者波谷
left_trend = right_trend;
}
return ret + 1; //把终点加上
}
};
最长递增子序列
这道到题目前面的记忆化搜索的文章中已经解决过了，这次用贪心算法的思想来解答
题目分析
但是上面这样的操作时间复杂度是On^2，并没有优化。这道题我们并不需要关系这个序列长什么样子，我们只关心最后一个元素是谁。
用二分来优化
代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> ret;
ret.push_back(nums[0]);
for(int i = 1; i < n; i++)
{
//大于最后一个元素不用二分，新开空间放入
if(nums[i] > ret.back())
{
ret.push_back(nums[i]);
}
else
{
int left = 0, right = ret.size() - 1;
//二分插入位置
while(left < right)
{
int mid = (left + right) >> 1;
if(ret[mid] < nums[i]) left = mid + 1;
else right = mid;
}
ret[left] = nums[i];
}
}
return ret.size();
}
};