贪心算法篇——万千抉择中的唯一考量，最优解追寻的跬步累积（2）

用户11379153

发布于 2025-11-05 16:19:18

800

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

引言

初篇我们介绍了贪心算法的相关背景知识，本篇我们将结合具体题目，进一步深化大家对于贪心算法的理解和运用。

一、柠檬水找零

1.1 题目链接：https://leetcode.cn/problems/lemonade-change/description/

1.2 题目分析：

一杯柠檬水售价5美元
每位顾客每次支付5，10或20美元，你必须正确找零
一开始手里没有零钱
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

1.3 思路讲解：

需要找零的时候只有两种情况

顾客付了10美元 此时只有一种找零方式，找顾客5美元
顾客付了20美元 此时有两种方式：

找顾客1张10美元，2张5美元（最优解）
找顾客3张5美元（次解）

根据贪心算法的思路，我们每次都需要求取最优解，并且推理可得，贪心解一定为最优解，因为5美元在该处相当于万能找零，而10美元只有在20美元这种特殊情况下才能派上用场。

1.4 代码实现：

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0,ten=0;//记录零钱
        for(auto e:bills)
        {
            if(e==5)
            {
                five++;
            }//5元时无需找零
            else if(e==10)
            {
                if(five==0)
                {
                    return false;
                }//无可找零钱时则直接返回false
                else
                {
                    five--;
                    ten++;
                }//能正常找零

            }
            else
            {
                if(five&&ten)
                {
                    five--;
                    ten--;
                }//最优情况，找一张10块，一张5块
                else if(five>=3)
                {
                    five=five-3;
                }//次之，找3张5元
                else
                {
                    return false;
                }//无法正常找零
            }
        }
        return true;
        
    }
};

二、将数组和减半的最少操作次数

2.1 题目链接：https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/

2.2 题目分析：

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择任意一个数并将它减小到恰好一半。
注意，在后续操作中你可以对减半过的数继续执行操作
请你返回将 nums 数组和至少减少一半的最少操作数。

2.3 思路讲解：

本题的贪心解很明显，每次减半时都选取当前数组的最大值进行减半操作，推理验证也可得贪心解即为最优解。

可以采取优先级队列的方式进行存储，这样每次top即可取出当前的最大值。

2.4 代码实现：

class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> heap;//创建大根堆
        double sum=0;
        int ret=0;//操作次数
        for(auto e :nums)
        {
            heap.push(e);
            sum+=e;

        }
        sum/=2;
        while(sum>0)
        {
            double t=heap.top();
            heap.pop();
            t/=2;
            sum-=t;
            heap.push(t);
            ret++;
        }//每次令最大的数减半
        return ret;
        
    }
};

三、最大数

3.1 题目链接：https://leetcode.cn/problems/largest-number/description/

3.2 题目分析：

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
输出结果可能非常大，所以你需要返回一个字符串而不是整数。

3.3 思路讲解：

将所有的数字当成字符串处理，那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。假设有两个字符串,10和2分别作为A和B 那么拼接后102<210，继续枚举即可发现规律

「A 拼接 B」⼤于「B 拼接 A」，那么 A 在前，B 在后；
「A 拼接 B」等于「B 拼接 A」，那么 A B 的顺序⽆所谓；
「A 拼接 B」⼩于「B 拼接 A」，那么 B 在前，A 在后；

问题就转化为：重新定义⼀个新的排序规则，然后排序即可。

3.4 代码实现：

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> str;
        for(auto e :nums)
        {
            str.push_back(to_string(e));
        }
        //排序
        sort(str.begin(),str.end(),[](const string& s1,const string& s2)
        {
            return s1+s2>s2+s1;
        });
        string ret;
        for(auto e:str)
        {
            ret+=e;
        }
        if(str[0]=="0") return "0";//处理前导0这种特殊情况
        return ret;
        
    }
};

四、摆动序列

4.1 题目链接：https://leetcode.cn/problems/largest-number/

4.2 题目分析：

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。
仅有一个元素或者含两个不等元素的序列也视作摆动序列。

4.3 思路讲解：

贪心策略

对于某⼀个位置来说： ◦ 如果接下来呈现上升趋势的话，我们让其上升到波峰的位置； ◦ 如果接下来呈现下降趋势的话，我们让其下降到波⾕的位置。因此，如果把整个数组放在「折线图」中，我们统计出所有的波峰以及波⾕的个数即可。

4.4 代码实现：

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return n;//处理特殊情况
        int ret=0,left=0;
        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;
        
    }
};