当前位置：首页 > news >正文

贪心策略实战Leetcode 860题：柠檬水找零问题的优雅解法

news 2026/5/11 23:41:34

贪心策略实战Leetcode 860题：柠檬水找零问题的优雅解法

📌 问题背景：一场贴近生活的算法考验
🧠 算法原理：贪心策略的核心逻辑拆解
- 核心思想
- 找零的逻辑分析
- 📊 算法步骤可视化（流程图）
💻 C++代码实现：简洁高效的贪心解法
- 核心代码
- 代码详解
- 性能分析
📝 算法总结与拓展
- 柠檬水找零问题的核心收获
- 贪心算法的拓展场景
🌟 写在最后

✨ 前言：在算法的世界里，贪心策略就像一把精巧的钥匙，总能以最直观、最高效的方式打开一类最优化问题的大门。它不追求复杂的全局推导，而是立足当下做出最优选择，最终收获全局的正确解。今天我们就以LeetCode 860题——柠檬水找零问题为例，拆解贪心策略的核心思想，用C++实现简洁高效的解题代码，带你感受贪心算法的独特魅力～

📌 问题背景：一场贴近生活的算法考验

我们化身街头柠檬水摊主，开启一天的摆摊之旅，却遇到了一个现实的问题：出摊时手上没有任何零钱，柠檬水定价为5元/杯，前来购买的顾客会随机支付5元、10元或20元的纸币，我们需要判断能否为每一位顾客顺利找零，让交易无间断完成。

这个问题看似是日常的找零场景，实则是典型的贪心算法应用案例，没有复杂的逻辑嵌套，核心在于每一次找零都做出对后续最有利的选择，这也是贪心策略的精髓所在。

🧠 算法原理：贪心策略的核心逻辑拆解

核心思想

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。区别于动态规划的全局规划，贪心的关键是局部最优选择能推导出全局最优解，而柠檬水找零问题恰好满足这一特性。

找零的逻辑分析

柠檬水单价5元，顾客支付面额仅为5、10、20元，我们只需维护手中5元、10元、20元纸币的数量（20元纸币仅作为收入，无法用于找零，核心关注5和10元），针对不同支付面额制定专属找零策略：

顾客支付5元：无需找零，直接增加手中5元纸币的数量即可；
顾客支付10元：需要找零5元，仅能使用5元纸币找零。若手中有5元则完成找零（5元数量-1，10元数量+1），若无则无法找零，返回false；
顾客支付20元：需要找零15元，有两种找零方案：
- 方案1：1张10元 + 1张5元（优先选择）
- 方案2：3张5元
✅贪心选择的关键：为什么优先选10+5的组合？因为5元纸币是找零的“通用货币”，10元仅能用于20元的找零，而5元可用于10元和20元的找零。保留更多的5元纸币，能为后续更多的找零场景提供支持，这就是局部最优选择，最终实现全局的找零成功。

📊 算法步骤可视化（流程图）

开始 | v 初始化：count5=0，count10=0，count20=0 | v 遍历每位顾客的支付金额cash | |---- cash ==5 → count5++ → 继续遍历 | |---- cash ==10 → 判断count5>0？ | | | |--- 是 → count5--，count10++ → 继续遍历 | |--- 否 → 返回false（找零失败） | |---- cash ==20 → 先判断count10>0且count5>0？ | |--- 是 → count10--，count5--，count20++ → 继续遍历 |--- 否 → 判断count5>=3？ | |--- 是 → count5-=3，count20++ → 继续遍历 |--- 否 → 返回false（找零失败） | v 所有顾客遍历完成 → 返回true（全部找零成功） 结束

💻 C++代码实现：简洁高效的贪心解法

核心代码

基于上述逻辑，我们用C++实现代码，代码仅需一次遍历（时间复杂度O(n)），常数级额外空间（空间复杂度O(1)），满足题目最优性能要求：

#include <iostream> #include <vector> using namespace std; // 柠檬水找零核心函数 bool lemonadeChange(vector<int>& bills) { int count5 = 0, count10 = 0, count20 = 0; // 记录三种纸币的数量 for (int cash : bills) { if (cash == 5) { // 支付5元，无需找零 count5++; } else if (cash == 10) { // 支付10元，需找5元 if (count5 == 0) return false; count5--; count10++; } else { // 支付20元，优先10+5找零 if (count10 > 0 && count5 > 0) { count10--; count5--; } else if (count5 >= 3) { // 无10元，用3张5元找零 count5 -= 3; } else { // 两种方案都不可行，找零失败 return false; } count20++; // 20元数量仅记录，不参与找零 } } // 所有顾客都完成找零 return true; } // 测试主函数 int main() { vector<int> test1 = {5,5,5,10,20}; // 测试用例1：找零成功 vector<int> test2 = {5,5,10,10,20}; // 测试用例2：找零失败 cout << "测试用例1结果：" << (lemonadeChange(test1) ? "成功" : "失败") << endl; cout << "测试用例2结果：" << (lemonadeChange(test2) ? "成功" : "失败") << endl; return 0; }