【算法学习计划】贪心算法（上）

目录

前言（什么是贪心）

leetcode 860.柠檬水找零

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

leetcode 179.最大数

leetcode 376.摆动序列

leetcode 300.最长递增子序列

leetcode 334.递增的三元子序列

leetcode 674.最长连续递增序列

leetcode 121.买卖股票的最佳时机

leetcode 122.买卖股票的最佳时机Ⅱ

leetcode 1005.K次取反后最大化的数组和

前言（什么是贪心）

这篇博客算是一个新的开端，因为一共有29道贪心将会在这个系列中被讲解

由于29道题目对于单篇博客太多了，所以我会将其分为上中下三个章节对其进行讲解，每一篇都有接近10篇贪心

而在开始之前，我们需要先讲解一下，贪心是什么，以及怎么样才算是贪

我们贪心其实就是只关注一个局部，从这个局部之中推导出应该怎么贪，并“希望”能够得到正确的解法

对的，就是希望，因为贪心不一定是正确的

我们就先用一道找零问题来举例子，

{40， 20， 10， 5， 1}，现在我们有一个数组，代表我们可以找给顾客的钱（买完饮料之后的找钱），假设客人给了48块钱，要我们用最少的钱的张数给客人找钱，那我们贪心的算法就应该是能用大额纸币就用大的，所以我们要贪心的话，就应该先用40块，然后发现还剩下8块，就是5+1+1+1这样子找钱

但如果现在数组是{40， 20， 16， 10， 5， 1}，我们在数组中加了一个16，那么贪心的话其实还是40+5+1+1+1，这是贪心，但是我们会发现16+16+16只用三张即可，所以证明我们贪错了

这就是我为什么说是“希望”能找到正确的答案

可能看到这里你会觉得，贪心有点像赌狗算法，但其实不然，因为正确的贪心是可以通过证明得出，这样子的贪心是绝对没有问题的，注意，是证明，严格的数学证明

比如我们为什么第一种情况可以，那是因为40后面是20，40代表两张20，我如果不用40，我就需要20+20，但这样子还不如一张40，后面的情况也是如此，所以我们这种贪心才是对的

但是第二种为什么是错的，因为并不对等，我这里的16是40无法取代的，所以才出现了问题

综上，贪心是一种关注局部的方法，可以通过证明来保证这样子贪是对的

还有一点需要大家注意的是，贪心想不出来是正常的！！！

就像田忌赛马，这也是贪心的一种，但所有人都能想出来吗？并不是

所以放平心态，学贪心就是学学别人是怎么贪的，积攒经验，下次再见到的时候就会了

（下文中的标题都是leedcode对应题目的链接）

leetcode 860.柠檬水找零

这道题目的解释在前言中被用做例子，这里就不再解释了

主要逻辑就是，优先选最大的数额找钱，还有就是，如果我们一刚开始是没有钱的，所以如果第一个元素不是 5 的话那就直接返回 false，接着如果我们在后面的找钱工作中有10块或者5块不够的情况的话，我们就返回false

另外，我们在收到 20 元的时候需要先判断一下，我们是否有一张 5 块和一张 10 块，有的话就用，没有的话就判断一下是否有 3 张 5 块，还没有就返回false，有的话就继续

代码如下：

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        if(bills[0] != 5) return false;
        int five = 0, ten = 0, twen = 0;    
        for(auto e : bills)
        {
            if(e == 5) five++;
            else if( e == 10)
            {
                if(!five) return false;
                five--, ten++;
            }
            else
            {
                if(ten && five) 
                    ten--, five--, twen++;
                else if(five < 3)
                    return false;
                else 
                    five -= 3, twen++;
            }
        }
        return true;
    }
};

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

这道题目我们的贪法就是，一直找最大的那个数，然后对其进行减半操作，每进行一次减半操作，我们就将记录减半次数的计数器++，当我们减少的数减少到数组总和的一半的时候，我们就跳出循环，然后返回计数器即可

首先，为什么我们这一道题目可以这么贪，假设我们第一个数不将最大的数减半的话，那么我们将其他任何一个数减半都没有这个数减的多（这就是体现了贪心的点，同时也是证明），所以我们这种做法一定是对的

我们每一次都减少当时最大数的一半，如果有其他做法的话，那么减半的必然不是最大的那个数，那么也必然没有这个数减的多

综上，我们可以创建一个大根堆，每次都将堆顶的元素取出来进行减半，当减到总和一半的时候，就退出

代码如下：

class Solution {
public:
    int halveArray(vector<int>& nums) 
    {
        priority_queue<double> heap;//默认大根堆
        double sum = 0;
        for(auto e : nums) heap.push(e), sum+=e;

        double n = sum; int in = 0; sum /= 2;
        while(n > sum)
        {
            double a = heap.top();
            heap.pop();
            n -= a/2;
            heap.push(a/2);
            in++;
        }

        return in;
    }
};

leetcode 179.最大数

这道题目算不上难，由于我们是将数字以字符串的形式拼接起来，所以我们就应该先对其排个序，以字符串的形式，我们直接取数字 a（假如有 30 和 8，那么字符串下的 8 是比 30 要大的，正好符合我们的要求），和数字 b，进行一个比较，看看是 a+b 的形式大一点还是 b+a 的形式大一点，因为 30 是比 3 要大的，如果直接拼接，那么303是没有330大的，所以我们需要比较

以这种方式排完序之后，直接从大到小拼接即可

这里我们可以用一个大根堆，比较前就将元素变成string类型，不用在比较的时候每一个都用上to_string，这样会块很多

当然你如果不喜欢用堆，那么直接堆原数组进行sort也可以，而博主我待会儿会将两种方法都放在下面，而我在排序的时候都是用的lambda表达式作为判断条件，这点看不懂的可以去deepseek一下

代码如下：

（一，使用堆的版本）

class Solution {
public:
    string largestNumber(vector<int>& nums) 
    {
        auto cmp_max = [](string& a, string& b){return a+b < b+a;};
        priority_queue<string, vector<string> ,decltype(cmp_max)> heap(cmp_max);

        for(auto e : nums) heap.push(to_string(e));
        if(heap.top() == "0") return "0";

        string res;

        while(!heap.empty())
        {
            res += heap.top();
            heap.pop();
        }

        return res;

    }
};

（二，在原数组上直接sort的版本）

class Solution {
public:
    string largestNumber(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end(), [](int& a, int& b)
            {return to_string(a)+to_string(b) > to_string(b)+to_string(a);});
        if(nums[0] == 0)return "0";

        string res;
        for(auto e : nums) res += to_string(e);

        return res;
    }
};

leetcode 376.摆动序列

这道题的贪心策略是要画图才能看出来的

我们看这张图，我们贪心的点就在于，我们可以直接找到每一个波峰和波谷，那就是我们摆动序列最长子序列的情况

试想一下，我们不选波峰的话，那么前面或者后面的数都没有波峰大，那么假如下一个波谷比我们选的数还要大的话，那么我们找到的长度就一定没有最优的情况要长

比如 5、16、30、20、27，其中 30 是波谷，假如我们不选30，选了 16，那么20对他来说就是升的情况后面的 27 就还是升，那么我们就会比最优情况长度要少

这其实就已经变相证明了这种贪心的可行性了，因为只有波峰波谷的情况是最优的，其他情况都没有这种的长度长或者最多和这种情况相等

另外还有一种情况就是相等的情况，这种，我们碰到相等的时候就跳过，判断就是判断下一个元素是否和当前元素相等，这样判断的原因是，我们在最后一个相等元素时，是不会被看作相等的，因为后面的数和他并不相等，而前面相等的数我们已经continue了，相当于只取了相等元素中的其中一个参与比较

代码如下：

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

leetcode 300.最长递增子序列

如果你想要学会这道题目的贪心策略的话，那么你需要先把dp版本的给学会先，因为这道题目的贪心策略就是根据dp推出来的（dp就是动态规划），另外，还需要学会二分查找，不然的话时间复杂度和dp是一样的都是O(n^2)，用了二分查找之后就是O(logN * N)

首先回顾一下dp版本，我们状态表示是以 i 位置为结尾，我们前面所有位置中最最长的递归子序列的长度是多少

也就是说，我们只关注那个递增子序列的最后一个元素，这个是关键，如果比这个最后一个元素大，那么我们就可以将这个元素接到后面，这个递增子序列的长度也就可以+1

所以我们可以创建一个数组，里面的每一个元素都代表以这个元素为结尾的递增子序列

然后，我们假设元素一和二分别是 7、2、6

那么我们先将 7 放入数组中，然后体现我们贪心的地方来了，我们选到 2 的时候，可以跟在 7 后面的元素，一定可以跟在 2 后面，所以我们就将 7 替换成 2

接着是 6，我们发现 6 是可以接在 2 后面的，所以我们就直接将 6 放在数组的第二个位置

可能有人看到这里还是不明白，我就总结一下，首先，这个贪心最终得出来的长度肯定是对的，但是里面的每一个元素大概率不是我们最优情况的元素

这是因为，我们见到小的就更新，大的就往后走的本质是，能接在情况A的数字，一定能接在情况B后面，这是一个一直在更新的，假如我数组中放的是 2、7、16，这代表的是三个不同的序列的结尾，16代表的是前面所有情况中长度为 3 的递增子序列的结尾位置的值，假设我先来来了一个数字 10 要来代替他，这就说明前面有情况（假设是2、7、10）这种情况和 2、7、16 的长度一样，都是 3，但是假如我下一个数字是 13 的话，接在 10 的后面能变成长度为 4 的情况，但是却不能接在 16 后面，前面两个元素（2、7）一直在更新代表的是后面的有长度也为 1 或者 2 的更优的情况，所以代表的是后面的序列

所以如果数组中后面的元素更新了的话，代表遍历到后面的时候，有更优但是长度相同的情况能代替这种情况

所以，还是那句话，dp中的是只关注最后一个元素的，我们这里也是一样，只用关注最后一个元素即可

最后，是我们二分查找算法的带入

我们将元素放入新开辟的数组中的时候，如果元素很多的话，那么我们还需要对这个数组遍历一遍，那其实就是 O(N^2) 的时间复杂度，但是这里面的数字是严格递增的，所以我们可以使用二分查找，在 O(logN * N) 的时间复杂度内解决这道题目

代码如下：

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
            {
                int left = 0, right = arr.size()-1;
                while(left < right)
                {
                    int mid = (left + right) >> 1;
                    if(arr[mid] < nums[i]) left = mid + 1;
                    else right = mid; 
                }
                arr[left] = nums[i];
            }
        }    
        return arr.size();
    }
};

leetcode 334.递增的三元子序列

这道题目不解释，就是上一道题目的简化版本，甚至都不需要新开辟数组和二分查找，只需要两个变量，如果有可以接在第二个变量后面的情况，就代表有三个元素的情况，那么直接return true 即可

代码如下：

class Solution {
public:
    bool 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) a = nums[i];
            else b = nums[i];
        }
        return false;
    }
};

leetcode 674.最长连续递增序列

对于这道题目，我们只需要知道一个点，就是，我现在有一个数，他比前面一个数要大，那么我就可以接在他后面，长度就应该是当前的最长长度

但是如果这个数，比前面的数要小，因为是连续的，这就意味着他只能从 1 开始（自身长度为 1），作为一个新的起点开始计数

可以想象一下，就相当于这个数组被分成了一个一个的小部分，互不相交，我们只需要找出这里面的最长的长度即可

代码如下：

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) 
    {
        int ret = INT_MIN;
        int count = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] > nums[i-1]) 
                count++;
            else
            {
                ret = max(ret, count);
                count = 1;
            }
        }    
        ret = max(ret, count);
        return ret;
    }
};

leetcode 121.买卖股票的最佳时机

当我们往后遍历的时候，我们已经知道前面所有元素中最小的元素是哪个了（定义一个变量，找到一个元素就比较一下就能找到前面所有元素中最小的那一个）

然后我们只需用    当前元素 - 最小值，得出来一个利润，找到最大利润即可

这题这样做是因为，我们只有一次交易机会

或者我们可以换一个思路，当我们将股票数据以折线图的形式画出来的时候，我们是能看到最低的波峰和最高的波谷的，将这两个对于位置的数字相减之后得到的就是结果，因为没有其他可能会比这个结果要大了

代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int min_val = prices[0], ret = INT_MIN;
        if(prices.size() == 1) return 0;
        for(int i = 1; i < prices.size(); i++)
        {
            ret = max(prices[i] - min_val, ret);
            min_val = min(prices[i], min_val);
        }    
        return ret < 0 ? 0 : ret;
    }
};

leetcode 122.买卖股票的最佳时机Ⅱ

我们所有的股票问题其实都能用dp来做，但不一定都可以用贪心，只不过贪心的情况代码会更好写，思路会更清晰，关键是，时间复杂度也会更低

这一题的关键词是，我们有无数次交易的机会，我们要的是最大的利润

那换一个角度想，我们要最大利润，那么我们是不是只要有利可图，我就直接交易

画成折线图就是：

我们图中的每一个上升的地方，都代表着利润，那么我们要利润最大，那就将这些利润全部加起来即可，这就是最大利润的情况了

然后如果是相等的情况，我们判不判断都无所谓，因为不判断，也就是加上一个利润为 0 的情况而已，并无变化，但是博主我还是判断了，也算是强迫症吧......

代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        if(n == 0 || n == 1) return 0;
        int left = prices[0], right = INT_MAX;
        int ret = 0;

        for(int i = 1; i < n-1; i++)
        {
            right = prices[i];
            if(prices[i] == prices[i+1]) continue;
            else if(prices[i] > left && prices[i] > prices[i+1])
            {
                ret += (right - left);
                left = right;
            }
            else if(prices[i] < left && prices[i] < prices[i+1])
                left = right;
        }    
        if(left < prices[n-1]) ret += prices[n-1] - left;

        return ret;
    }
};

leetcode 1005.K次取反后最大化的数组和

这道题目其实没什么好讲的，因为我们的贪法就是一直对最小的那个数进行操作（前提是这个数为负数）

所以我们可以先对这个数组进行一个排序，默认的升序即可

然后在最前面的数字都是最小的数字，我们只需要判断，这个数字是否是负数，如果是的话就将这个数转换成整数，并且 k--，而如果 k 已经减小到 0 了或者这个数组里面已经没有负数了，我们就需要退出了

出来之后我们还需要进行一次排序，因为我们有可能会这样：

-5、-3、0、2、5          k=1

5、-3、0、2、5           k=0

我们会发现有负数就在中间，再次排序其实就是更新一下数组而已

然后我们就需要判断了，如果 k 还有的话，那就意味着数组里面必然没有负数了，因为有负数的话会 k-- 然后转化为正数，所以我们就可以再进行一次分类讨论，也就是 k 是奇数还是偶数

如果是奇数，那么前面所有的偶数次我们都可以对同一个元素使用，最后一次我们只能对最小的那个元素使用，所以就是所有元素相加之后减去两个第一个元素（当然你也可以在相加的时候不加第一个元素，然后减的时候只减一次即可）

然后是 k 为偶的情况，我们直接数组内全部相加即可

接着如果 k 已经没了，也是只需要将数组里面所有元素相加即可

代码如下：

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) 
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; i++)
        {
            if(k == 0 || nums[i] >= 0) break;
            if(nums[i] < 0) nums[i] = -1 * nums[i], k--;
        }    
        int sum = 0, flag = 0;
        sort(nums.begin(), nums.end());
        for(auto e : nums) 
        {
            sum += e;
            if(e == 0) flag = 1;
        }
        if(k == 0) return sum;
        else
        {
            if(k % 2 == 1 && flag == 0) return sum -= 2*nums[0];
            else return sum;
        }
        return 0;
    }
};

今天这篇博客到这里就结束啦~(￣▽￣)~*

如果觉得对你有帮助的话，希望可以关注一下喔

另外，博主还会尽快更新中和下，届时会将链接放到这篇文章之中，觉得讲得好的也可以关注一下喔

最后，如果你有什么疑问，可以直接私信我或者在评论区留言，博主看到了的话一定会为你答疑的