贪心算法（1）

目录

 柠檬水找零

题解：

代码：

将数组和减半的最少操作次数（大根堆）

题解：

代码：

最大数（注意 sort 中 cmp 的写法）

题解：

代码：

摆动序列（如何判断波峰、波谷、平台）

题解：

代码：

---

贪心策略：

解决问题的策略：局部最优-> 全局最优

1、把解决问题的过程分为若干步；

2、解决每一步的时候，都选择当前看起来“最优的”解法；

3、希望得到全局最优解。

 柠檬水找零

860. 柠檬水找零 - 力扣（LeetCode）https://leetcode.cn/problems/lemonade-change/description/

题解：

假设当前顾客付了 5 美元，则无需找零，摊主手中 5 美元的张数+1；

假设当前顾客付了 10 美元，那么摊主需要返还 5 美元：

• 如果摊主手中有 5 美元，则摊主手中 10 美元的张数 +1，且返还顾客 5 美元，即摊主手中 5 美元的张数 -1 ；
• 如果摊主手中没有 5 美元，说明摊主此时无法找零，直接返回 false；

假设当前顾客付了 20 美元，那么摊主需要返还 15 美元：

• 如果摊主手中有 10 美元 和 5 美元，则摊主手中 10 美元和 5 美元的张数都 -1；
• 如果摊主手中有 3 张 5 美元，则摊主手中 5 美元的张数 -3；

在可以找零的这两种情况中，就可以体现贪心策略。可以发现在找零的过程中，5 美元经常使用，所以不能让 5 美元的张数太快消耗完，可能会影响后面找零，所以在返还 15 美元的情况下，应该优先返还 1张 10 美元和 1张 5 美元，其次选择返还 3张 5 美元。

代码：

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int ten=0,five=0;for(auto x:bills){if(x==5)    five++;else if(x==10){if(five>0){five--;    ten++;}else    return false;//无法找零}else//x=20{if(ten>0 && five>0)//找10+5{ten--;  five--;}else if(five>=3) five-=3;//没有10，找5+5+5else    return false;//无法找零}}return true;}
};

将数组和减半的最少操作次数（大根堆）

2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/ 

题解：

数组减半的最少操作数，其实就是找到数组中的最大值，并将其减半，为了方便找到数组的最大值，可以使用大根堆，找到堆顶元素，将其减半后再次放回大根堆中，直到数组和减半，就可以得出最少操作数。

代码：

class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> p;double sum=0.0;for(auto x:nums){p.push(x);sum+=x;}sum/=2.0;int count=0;while(sum>0){double tmp=p.top();p.pop();tmp/=2.0;sum-=tmp; p.push(tmp);count++;}return count;}
};

最大数（注意 sort 中 cmp 的写法）

179. 最大数 - 力扣（LeetCode）https://leetcode.cn/problems/largest-number/description/

题解：

以示例一为例，数字 10 和数字 2 拼在一起，会得到数字 102 和数字 210，由于 210 > 102，所以返回 210；

以示例二为例，我们可以对数组排序：

数字 3 和 数字 30 拼在一起，得到数字 330 和 数字 303，由于 330 > 303，所以 数字 3 和 数字 30 排序后为 [ 3 , 30 ] ；

数字 30 和 数字 34 拼在一起，得到数字 3430 和数字 3034，所以排序结果为 [ 34, 30 ]，数字 34 再和 数字 3 拼在一起，得到343 和 334，所以最终排序结果为 [ 34 , 3 , 30 ]；

用这个规则排序后得到的数组为 [ 9 , 5 , 34 , 3 , 30 ]，最终拼到的最大数为 9534330。

可以看出排序的规则就是把两个数 a 和 b 拼在一起，拼接后的数为 ab 和 ba，

• 若 ab > ba，a 就排在 b 前面；
• 若 ab < ba，b 就排在 a 前面。

为了方便拼接和比较大小，可以把数字都转换为字符串，比较拼接后字符串的字典序，

• 字典序 ab > ba ，a 排在前面;
• 字典序 ab < ba ，b 排在前面。 

代码：

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> str;for(auto x:nums){str.push_back(to_string(x));}sort(str.begin(),str.end(),[](const string s1,const string s2){   return s1+s2>s2+s1; });string ret;for(auto x:str)ret+=x;if(ret[0]=='0') return "0";else return ret;}
};

摆动序列（如何判断波峰、波谷、平台）

376. 摆动序列 - 力扣（LeetCode）https://leetcode.cn/problems/wiggle-subsequence/description/

题解：

以示例二为例，将数字的升降趋势画出图：

可以看出图中存在波峰（极大值），波谷（极小值），波峰和波峰左、右边的数的差值恰好一正一负， 波谷和波谷左、右边的数的差值恰好一正一负， 满足摆动序列的条件，即数组中所有的极大值和极小值构成的子数组就是题目所说的摆动序列，我们只需要得到摆动序列的长度即可。

判断一个数和这个数左边的数的差值为 left，和右边的数的差值为 right，判断 left * right 是否小于 0 就可以知道这个数是不是极大/小值。

同时，数组最左端和最右端的数也可以视为极大值或极小值，也应该被计入摆动序列中，但最左端的数左边没有数字了，最右端的数右边没有数字了，没办法用 left * right 的积是否小于 0 来判断是否为极大/小值。

• 针对最左端的数，我们将 left 初始化为 0，left * right 为 0，摆动序列的长度 +1，就可以解决最左端的问题；
• 针对最右端的数，在整个数组判断完 left * right 之后，得到的摆动序列的长度 +1 即可。

但是 left * right == 0 还有以下特殊情况，也就是出现了平台：

1、数组中连续的几个数的数值相等，即 right = 0，但这几个数总体是呈现上升或下降趋势的，并没有极大/小值：

2、数组中连续的几个数的数值相等，即 right = 0，但这几个数中总体上是存在极大/小值的（把这几个数值相同的点视为一个点的话）：

 

当 right = 0 时，说明存在平台，我们可以跳过平台， 不要计算 left * right，避免与最左端的情况的判断混淆，跳过平台后，left 是平台左边的差值，right 是平台右边的差值，

left * right < 0 则摆动序列的长度 +1（该平台中存在极大/小值，选择平台中的任意一点计入摆动序列即可）。

代码：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int left=0,ret=0,n=nums.size();for(int i=0;i<n-1;i++){int right=nums[i+1]-nums[i];if(right==0)    continue;//平台else if(left*right<=0)  ret++;//存在波峰或波谷left=right;}return ret+1;//数组的最左/右端也算是波峰/波谷}
};