【贪心算法】贪心算法一

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.柠檬水找零

题目链接： 860. 柠檬水找零

题目分析：

这里有两点需要注意：

1. 顾客排队购买你的产品
2. 一开始你手头没有任何零钱，你要拿着顾客的钱去找钱

顾客排队购买你的产品，也就是说如果第一个顾客给你10或者20美元你就找不了，返回false。

算法原理：

这里我们只关注正确的贪心策略，不用管它怎么来的。最后我们来证明一下。

贪心可不是上来就贪，而是在分析问题的过程中，发现可以贪，我们才贪。

这道题就是一个找零问题，顾客会给5美元，10美元，20美元。我们分情况给他找钱就可以了。

当顾客给5块钱，我们直接收下就行了

当顾客给10块钱，我们要找5块钱，顺手把10块钱收下，但是找5元前提是我们有5块钱可以找，如果没有返回false

当顾客给20块钱，关于20块钱找零其实我们有两种策略，
第一种：找一张10块钱，在找一张5块钱
第二种：找三张5块钱

此时就有分歧了，我们要想哪一种最好，这就体现了贪心。贪心就体现在这一步，我们应该选择更优的策略来完成这个找零工作。

到底那个优秀，其实是根据5块钱来的，5块钱不仅完成20块钱找零工作，还能完成10块钱找零工作。因此我们尽量保留5块钱。

所以看起来当前最优策略就是第一种策略。如果第一种策略不成立，我们再选第二种策略，如果第二种策略都不成立就返回false

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for(auto e : bills)
        {
            if(e == 5) five++;
            else if(e == 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;
    }
};

证明：贪心策略是正确的

证明策略：交换论证法

假设
贪心策略解决这道题的方法顺序是：a、b、c、d、e、f，
最优解解决这道题的方法顺序是：e、b、c、d、a、f

此时如果在不破坏最优解的 “最优性质的” 前提下，能够将最优解调整成贪心解。那我们就说贪心解就是最优解。

这就是我们的交换论证法，交换论证法的核心就是找到不破坏最优性质的前提下把假设出来的最优解逐步的调整出贪心解。

如果顾客给我们5美元或者10美元，贪心解和最优解是没有区别的。5块就收下，10块就找5块。

唯一的区间就是20美元

贪心解策略是有限选择10+5，但是最优解有可能和贪心解不一样选择的是5+5+5。如果一样肯定不考虑，考虑的肯定是不一样的情况。

假设从左往右扫描第一次碰到20美元下不同的时候，我们看看能不能把最优解调整成贪心解。

其实就盯着10美元就可以了。因为贪心解这里用到10，最优解这里没有用到10。那么此时10美元就有两种情况了，第一种情况10美元在后面找零过程没有用到，也就是贪心解用来10，但是最优解在后面的找零操作并没有用到10，10块钱装到兜里了。那么此时我们就可以把最优解的两个5替换成兜里的10块钱。这个替换并不影响最优性质，因为这个10在后面找零操作就没有用过。

最优解能解决问题，替换完之后的10也能解决问题

第二种情况，10美元在后面的换零操作有一次用过了。此时我们依旧可以把前两个5用后面的10交换。前面用10，后面用两个5，交换后依旧不影响最优性质。然后又和贪心解一模一样。

你会发现最优解用或者不用10，都可以把它替换成和贪心解一样的形式。也就说从前往后扫描只要不相等就调整，那最终一定能把最优解逐步调整成贪心解，并且最优解是可以解决问题，那贪心解也一定能解决问题。所以贪心解就和最优解是等价的。

2.将数组和减半的最少操作次数

题目链接： 2208. 将数组和减半的最少操作次数

题目描述：

算法原理：

这道题把题意搞清楚之后，想让我们用最少的操作次数把数组和至少减少到之前的一半，那我们肯定会想到每次挑选的时候挑选当前数组里最大的数给它减半，因为挑数组最大的数减半才有可能最快的把整个数组的和减少到之前的一半。

解法：贪心

具体策略：每次挑选当前数组中，最大的那个数，然后减半，直到数组和减少到至少一半为止。

实现我们这个策略的核心就是循环这一步，每次挑选当前数组中，最大的那个数。如果每次都去遍历数组挑最大的那个数，时间复杂度是非常恐怖的，这里我们可以使用优先级队列这个数据结构建立一个大根堆。

解法：贪心 + 大根堆

class Solution {
public:
    int halveArray(vector<int>& nums) {

        priority_queue<double> heap;
        double sum = 0.0;
        for(auto e : nums) 
        {
            heap.push(e);
            sum += e;
        }
        sum /= 2.0;
        
        int count = 0;
        while(sum > 0)
        {
            double t = heap.top() / 2.0;
            heap.pop();
            sum -= t;
            count++;
            heap.push(t);
        }
        return count;
        
    }
};

证明

证明策略：交换论证法

这里在说明一点，不管用什么方法证明，一定得要结合题意和贪心策略来证明。

我们这里的题意是每次挑选一个数直到数组和减半，
假设贪心解每次挑选数，这里用横线上面的点表示每次挑选的数。同样最优解也是这样表示。贪心解挑选的数个数大于或者等于最优解的数个数。

我们只要能想到一个转化规则，在不破坏最优解的 “最优性质的” 前提下，能够将最优解调整成贪心解。就可以了。

那我们从左到右扫描贪心解和最优解。先找到第一次两者不一样的地方。假设贪心解挑的是x，最优解挑的是y，此时我们只要能把y变成x就可以了。

如何变，紧扣题意和贪心策略，在我们贪心解里面挑的数组中最大的数，最优解如果没有挑最大那个数，那么这里有一个不等式，x > y

对于x在最优解中它有两种情况，第一种情况，x没有用过。此时可以大胆将y替换成x，因为x > y，你用一个小的数减半就能让整个数组和减半，那选一个更大的数减半那更能让整个数组和减半。即使后面有y/2，y/4等都可以用x替换y。

第二种情况，x在后续最优解使用了，那我们依旧可以将y与x交换。因为在最优解先用x减半和后用y减半并不影响最优解的最少操作次数。即使在y和x中间可能使用了y/2，y/4，但是把y交换到后面去了，那就没有y/2，y/4这些数，那逻辑不就错了吗。其实可以把y和x交换完之后，把y/2，y/4，y重新排一下序，还是 y，y/2，y/4的使用。

此时我们在处理最后一个情况，贪心解的次数可能是比最优解次数多的，但是这种情况是绝对不可能的，因为我们从前往后扫描的时候，只要遇到不同都可以用这两种情况进行调整。所以说当最优解解决完情况后，贪心解也一定减半了。所以最优解的操作次数和贪心解的操作次数是一样的。

到这里就证明完毕了。原因就是从前往后扫描两个解的时候，只要有一个地方不一样，就可以通过这两个策略进行调整，所以最优解就可以在不失去最优性的前提下转化为贪心解。所以当最优解是最少操作次数解决这个问题的时候，贪心解也是最少操作次数解决这个问题的时候。

3.最大数

题目链接： 179. 最大数

题目分析：

示例1，[10，2] 它所形成的最大整数就是这个数组里面按照从左往右的顺序把数拼起来就可以了。比如这个数组不去休息顺序从左往右拼起来就是102，如果调整一下顺序拼接就是210，201显然大于102，所以示例1所能拼成的最大整数就是210.

但是有可能输出结果可能非常大，所以你需要返回一个字符串而不是整数。

算法原理：

如果把这道题的题意搞清楚之后会发现这道题特别像是一道排序题。无非就是给一个数组按照它给的规则把数组排下序使其形成一个最大的数。

所以先回忆之前正常的排序看能否给我们这道题带来一些启发

正常的排序（升序）
[4，10，8]

不管是之前学习过的冒泡，快排，归并等排序，它们都是干一件事情，就是确定这些元素的先后顺序。只要能搞清楚这些元素谁在前面、谁在中间、谁在后面，我们就能完成这些元素的排序。

所以正常的排序本质：确定元素的先后顺序：谁在前，谁在后。

其中确定元素的先后顺序是根据一定的排序规则来确定

本题的排序其实也是在确定元素的先后顺序，所以我们仅需找一个排序规则就可以了。

排序规则，其实例一[10，2]已经给我们了，先把这两个数拼接成102和210，然后我们会发现把2放在前面把10放在后面是优于102，因此我们得到一个结果把2放前面，10放后面。

我们可以把这两个数抽象出来，a表示第一个数，b表示第二个数。
此时我们会得到两种情况，要么a在前b在后，要么b在前a在后

如果发现a在前b在后这种拼接是优于把b在前a在后的拼接，我们可以得到a可以放放在前面，b放在后面。

如果发现b在前a在后这种拼接和把a在前b在后的拼接是一样的，那就无所谓。

如果发现b在前a在后这种拼接是优于把a在前b在后的拼接，我们可以得到b可以放放在前面，a放在后面。

这就是我们这道题里面的排序规则。基于这样的排序规则会发现它们俩是非常一样的，这里我们可以使用sort进行排序，然后把这个比较规则传给sort。

1. 我们这个专题不是贪心吗，但是这里贪心体现在哪里呢？

其实贪心就体现在了比较规则，确定谁前谁后的策略就是贪心。

2. 这一个排序规则，为什么能排序呢?

之前排序规则之所以能排序最重要的就是传递性。a > b，b > c ----> a > c，可以推出来 a 在 b 前面，b 在 c 前面，又因为 a > c，所以 a 在 c 前面。所以符合 a b c。

如果此时a > b，b > c 推不出来 a > c，就不能排序。因为a > b 可以推出 a 在 b 前面，b > c 可以推出 b 在 c 前面，如果推不出来 a > c 的意思是 c 可能大于 a，如果 c > a ，那 a 就在 c 的后面，此时根本就不可能。数组就不能排序。

上面传递性太明显了，所以极有可能会忽略，但是我们这道题不能忽略这一点。如果知道 ab > ba，bc > cb 推出 a 在 b 的前面，b 在 c 的前面，如果在能知道ac > ca a 在 c 的前面，才能摆出 a b c

但是能不能推出这一点，需要后面去证明。

这里写代码还有两个细节问题：

第一个细节：把数转化成字符串，然后拼接成字符串，比较字典序。

如果不这样搞还需要算两个数有多少位，然后一个数乘于位数在加上另一个数才能得到一个拼接的数。

第二个细节：这道题有可能传递 [0，0]这样的数组，如果按照之前的策略那就会返回一个 “00” 字符串。但是我们要的是一个数，我们要把字符串搞成 “0” 才行。我们可以判断一下最后的结果ret，如果第一个字符是 “0” 说明后面应该全都是 “0”，那我们最终返回 “0” 这个字符串就可以了。为什么后面应该全都是 “0”，如果后面的是不是0的话，0放在最后一个位置绝对不可能是最大数。

class Solution {
public:
    string largestNumber(vector<int>& nums) {

        // 优化: 把所有的数转化成字符串
        vector<string> strs;
        for(int x : nums) strs.push_back(to_string(x));

        // 排序
        sort(strs.begin(), strs.end(), [](const string& s1, const string& s2)
        {
            return s1 + s2 > s2 + s1;
        });

        // 提取结果 
        string ret;
        for(auto& s : strs) ret += s;
        if(ret[0] == '0') return "0";
        return ret;

    }
};

证明：

这里我们只要证明我们这个策略是可以排序的就可以了。

如何证明一个东西可以排序呢？这里要用到数学的知识。

证明方法：数学知识（全序关系）

全序关系的用处：假设有一个集合，集合里有很多元素，全序关系的作用就是从这个集合中任意挑选两个元素，如果这两个元素在定义的比较规则下，如果满足全序关系的话，我们就说这个集合是可以排序的。

全序关系分为三个性质，也就是说只要满足三个性质就有全序关系。

1. 完全性

从集合中任意挑选两个元素 a、b，它必定会存在两个关系的一个，要么 a <= b，要么 a >= b。如果挑选的两个元素压根没有大小关系，根本不知道谁在前谁在后。所以完全性就是能够排序的最前提条件：任意挑选两个元素能够比大小。

2. 反对称性

还是任意挑选两个元素a、b，如果知道 a <= b 且 a >= b，那必须能够推出 a = b，如果得不到这个结果，那么整个数组排序把a放在前面b放在后面是一种排序结果，把b放在前面a放在后面还是一种排序结果。那么整个集合就不能排序，因为整个集合要想排序那最终结果是唯一的才行。

3. 传递性

任意挑三个元素a、b、c，如果 a >= b，b >= c，那一定要推出a >= c 。这一点上面已经说过了如果不满足排序不出来最终结果。

我们要证明的是排序规则，任意挑两个数a、b，然后看 ab 和 ba 这个情况的大小，然后确定a和b的前后顺序。

1. 证明完全性

挑出a、b，然后看a拼接b，b拼接a是能够比大小的就可以了。

第一种证明：

ab拼接后是一个数，ba拼接后也是一个数。数和数之间是能够比大小的。要么ab >= ba，要么 ba >= ab。

第二种证明：

设a的位数为 x 位， b的位数为 y 位。
ab拼接的结果是可以表示出来的：10^ya + b
ba：10^xb + a

既然这两个数能明确表示出来，那一定能比大小。

2. 证明反对称性

如果 ab <= ba 且 ab >= ba，那我们要能得到 ab = ba 这个结论。

将ab和ba用刚才的进行处理，因为这里是一个一个的数，设ab为m，ba为n，此时我们能得到一个夹逼定理。m <= n <= m，我们可以得到 m = n。所以我们可以根据1、2得到3。

3. 证明传递性

还是任取三个数a、b、c，如果ab >= ba 且 bc >= cb 我们必须要推出来ac >= ca
，ac >= ca的意思是a在前c在后，也就是说a在前，b在后，我们要能推出来a在前，c在后才行。

我们证明方法和上面一样，把不等式写成一个确切的数

这里特殊情况要考虑一下，如果a、b、c其中任意一个可能等于0， 假如a是0的话，那x位数就是为0。小学我们就知道0不是一个个位数，但是这道题里我们把0这个数当成一个个位数。如a是12，b为0，ab为120

如果能由1和2这两个式子能推出来第3个式子，那么这个式子就成立

我们观察一下三个式子发现第三个式子是没有b的，因此我们仅需通过1和2两个式子把b给消掉就可以了。我们可以把b的系数移过去就可以把b消掉，但是移系数要注意系数不能为0，但是刚才处理特殊情况的时候说过x绝对不可能等于0的，那么10^x绝对不可能等于1，所以我们可以大胆移第一个式子b的系数。同样第二个式子也是。

10^y - 1不可能为0，两步同时消掉，然后在移项就可以得到第三个式子

到此证毕，我们这个排序规则既有完全性，又有反对称性，又有对称性，因此具有全序关系。有全序关系就说明我们这里定义的排序规则是可以排序的。

4.摆动序列

题目链接：376. 摆动序列

题目分析：

摆动序列就是一上一下。注意仅有一个元素或者含两个不等元素的序列也视作摆动序列，返回摆动序列 的 最长子序列的长度。

算法原理：

这里我们就不写具体的数了，而把数当成折线图的形式。目前先不考虑水平这样的形式，先考虑相邻两个元素不同的形式，最后在把水平的处理一下

如果图是这样的，如何找它的最长摆动序列呢？
我们肯定有这样的想法，把左边和右边的点挑出来，然后在把所有极大值点和极小值点也挑出来，所形成的序列就是一个最长摆动序列。

这个策略确实是可以的，我们的贪心策略最终也和这个策略长的一样。

接下来我们就来贪一下，我们要找到的是最长摆动序列，相当于就是在这个图中尽可能的挑一些点出来所形成的序列是摆动序列。

既然是尽可能挑多的点，那第一个点就给选上，接下来挑选第二个点的时候继续贪，当前右边这么多点我选择那个点看起来是最优的，此时就有分情况讨论的过程

第一种情况在上升的线上选一个点，但是在上升的这条线上选都没有第三种情况好，因为选了上升线上一个点接下来要去选下降的，如果挑选这些较小上升的点，那在挑选下降的点可供选择的空间就小了。比如画×的点就选不到了。

第二种情况选择右边的某个点，如果选了这个点，那摆动系列绝对不可能是最长的，因为中间还有可以选择的一上一下的点。

同样选了这个点也会错失一个拐点，那摆动序列也不会是最长的。

可能还会选这条下降线的点，有可能是会最长的，但是并不保险，有可能这条线没有点，所以不如选第三种情况这个点。

固定两个点之后，考虑第三个点依旧和选择第二个点一样分情况讨论，如果是下降选择不能在下降的点，如果是上升选择不能在上升的点。直到所有点都选完，就是最长摆动子序列。

你会发现我们贪心挑选出来的点就是把极大值和极小值还有两个端点的值跳出来。

贪心：统计出所有的波峰以及波谷的个数
然后在把左右两个点加上就可以了。

那如何统计出最终的结果呢？

首先如何确定一个点是波峰还是波谷，

波峰：当前这个点减左边的点如果是正，右边的点减去当前的点如果是负，就是波峰。

波谷：当前这个点减去左边的点如果是负，右边的点减去当前的点如果是正，就是波谷。

也就是说当前这个点左右是相反的就可以确定要么是波峰要么是波谷。

还有一个问题，如果相邻两个元素是相同的就麻烦了，它会分成两大类，
第一类：相同的时候左右增减趋势是相同的
第二类：相同的时候左右增减趋势是相反的

第一类是没有波峰波谷的，第二类是有的。虽然是有相同的元素，但是第一类总体要么上升、要么下降，不需要统计波峰波谷。第二类要么下降后上升、要么上升后下降，是需要统计波峰波谷的。

但是相同元素该统计那一个呢？并且虽然属于不同类，但是都是左边是是负数右边是0一个不需要统计一个需要统计，还是很恶心的。

可以用一个变量left记录当前某个点左边的增减趋势，然后上述情况的时候，把这些相同的情况都可以忽略掉。仅需考虑最左边点的增减趋势和最右边点的增减趋势。

接下来模拟一下，

left就是标记某个点左边的正负，它有三种情况

left = 0（表示第一个点左边既可以上升也可以是下降的）
left > 0（上升）
left < 0（下降）

然后确定某个点的时候仅需算一个它的右边right就行了，right = nums[i+1] - nums[i]
，当left*right <= 0 就是波峰或者波谷，当right = 0 说明遇到相同的元素然后是可以抛弃的，

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return n;
        
        int left = 0, right = 0, ret = 0;
        for(int i = 0; i < n - 1 ; ++i)
        {
            right = nums[i + 1] - nums[i];
            if(right == 0) continue;
            if(left * right <= 0) ++ret;
            left = right;
        }
        return ret + 1;
    }
};

证明：

这道题证明有三种方法：

1. 反证法
2. 分类讨论
3. 交换论证法

这里我们证明方法是反证法：

假设我们的操作是错的，此时它的反命题就是一个正确的，只要我们证明正确的命题是有矛盾的或者有错误的，那原来的命题就是正确的。

我们的贪心解是选择左右端点和极值，假设最后选择的点为n，这里 n = 6

假设贪心解是错的，那必须会存在一个最优解，在相同的情况下可以选择更多的点，N > 6。我们只要推出最优解是矛盾的或者错误的，那我们贪心解就对了。

盯着每一个拐点，先看最左边的拐点，我们这是一个连续的区间，左边元素比它小，右边元素也比它小，在它这个左右区间里一定会出现一个极大值，要么该点是极大值点要么就是区间内的其他点。

在看下一个拐点，左右两侧都是比它大的，又因为是连续的，所以在这个区间里面必定会存在一个极小值。

同理后面也可以得到极大值，极小值。

因此可以推出在最优解里，极值点个数是N-2（舍去左右两端点），但是这个N-2是不存在的。因为在贪心解里面我们是可以推出来极值点个数是n-2=4，因为最优解N>6，所以它的极值点个数是N-2 > 4的，但是极值点个数是不可能大于4的，所以最优解压根就是不存在的，因为贪心解得到极值点个数是4，你这个最优解算出考虑极值点个数大于4，这是不符合实际情况的。所以这个最优解是不存在的，因此贪心解是正确的。