本文档提供了对贪心算法、其属性、应用和在Interviews仓库中的实现的全面概述。贪心算法在每一步都做出局部最优选择，旨在找到全局最优解，而不重新考虑之前的决策。本页涵盖了贪心算法的基本原理、何时应用它们、来自仓库的示例以及对其效率的分析。
贪心算法的特点是其简单的决策启发式：做出当下看起来最好的选择。要使用贪心方法解决问题，它必须表现出两个关键属性：
这些属性将贪心算法与其他方法（如动态规划）区分开来，动态规划通常需要探索多种路径来找到最优解。
贪心算法特别有效，当
然而，贪心算法并非总是适用。许多优化问题需要考虑多种路径或重新审视过去的决策才能找到最优解。在这种情况下，像动态规划这样的方法可能更合适。
| 适用于贪心 | 不适用于贪心 |
|---|---|
| 活动选择 | 最长回文子串 |
| 霍夫曼编码 | 背包问题（通用） |
| 最小生成树 | 最长公共子序列 |
| 区间调度 | 大多数最短路径问题 |
| 硬币找零（特定面额） | 旅行商问题 |
如仓库所示，当硬币的面额满足特定属性时，硬币找零问题可以使用贪心方法解决。
问题：给定硬币面额（一分：1美分，五分：5美分，十分：10美分，二十五分：25美分）和一个目标金额（例如，41美分），找出使该金额所需的最少硬币数。
贪心方法:
注意：贪心方法适用于这组特定的面额（美国硬币），但不能保证适用于所有面额。例如，如果我们有面额为 {1, 3, 4} 的硬币，想组成 6，贪心算法会给出 3 枚硬币（4+1+1），而不是最优的 2 枚硬币（3+3）。
此问题展示了仓库中贪心算法方法的实际应用。
问题：给定一个数组，其中第 i 个元素表示第 i 天的股票价格，找出买卖股票的最大利润。您可以完成多次交易，但必须在再次购买之前出售。
贪心方法:
实现:
仓库中的解决方案leetcode/greedy/BestTimeToBuyAndSellStockII.java7-20直接实现了这种贪心方法。
该算法演示了一个案例，即做出局部最优选择（只要第二天能获利就买入）可以带来全局最优解决方案（最大可能利润）。
来源：leetcode/greedy/BestTimeToBuyAndSellStockII.java1-21
理解何时使用贪心算法与动态规划至关重要。
为了说明这种区别，让我们将“最佳股票买卖时机 II”的贪心解决方案与“房屋抢劫犯”的动态规划解决方案进行比较。
| 问题 | 最佳股票买卖时机 II | 房屋抢劫犯 |
|---|---|---|
| 方法 | 贪心法 | 动态规划 |
| 核心决策 | 尽可能抓住利润 | 选择包含当前房屋或跳过它 |
| 是否重新考虑过去的决策？ | 否 | 是（通过 DP 表） |
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(1) | O(n) |
来源：leetcode/greedy/BestTimeToBuyAndSellStockII.java1-21 leetcode/dynamic-programming/HouseRobber.java1-26 company/airbnb/HouseRobber.java1-26 company/linkedin/HouseRobber.java1-26
许多经典的计算机科学问题都可以用贪心算法解决。
这些问题中的每一个都已证明贪心解决方案能够保证最优结果。
与动态规划或回溯方法相比，贪心算法通常具有更好的时间和空间复杂度。
| 方面 | 贪心法 | 动态规划 | 回溯 |
|---|---|---|---|
| 时间复杂度 | 通常 O(n) 或 O(n log n) | 通常 O(n²) 或更差 | 可能是指数级的 |
| 空间复杂度 | 通常 O(1) 或 O(n) | 通常 O(n) 或 O(n²) | 通常 O(n) 用于递归栈 |
| 实现 | 更简单，迭代 | 更复杂，使用记忆化 | 递归，分支探索 |
对于此仓库中的示例
来源：leetcode/greedy/BestTimeToBuyAndSellStockII.java1-21 README.md289-307
与动态规划不同，动态规划的正确性通常更容易建立，但证明贪心算法能产生最优解可能具有挑战性。证明通常涉及显示
例如，在硬币找零问题中，使用标准的美国面额，可以证明在每一步选择最大可能硬币会得到所需的最小硬币数，因为每个面额都是较小面额的倍数或近倍数。
当局部最优导致全局最优时，贪心算法为解决优化问题提供了一种有效的方法。关键属性包括：
Interviews 仓库包含了演示贪心原理在实际问题中应用的示例，特别是 BestTimeToBuyAndSellStockII 中的股票交易场景。
在评估是否使用贪心方法时，请仔细分析问题是否同时具有最优子结构和贪心选择性质。
来源：README.md289-307 leetcode/greedy/BestTimeToBuyAndSellStockII.java1-21
刷新此 Wiki
最后索引时间2025 年 4 月 18 日(a70c22)