一、什么是贪心算法？

贪心算法（Greedy Algorithm）是一种在每一步都采取当前状态下最佳（即最有利）的决策，最终达到问题整体最优解的方法。它的主要特点是 每一步决定都是不可逆 ，只关注眼前的收益，不考虑整体或长期影响。

贪心算法的两个核心性质

贪心选择性质： 整体最优解可以通过一系列局部最佳选择获得，每一步决策无需依赖前后信息，仅基于当前状态。

最优子结构性质： 一个问题的最优解包含了其子问题的最优解，即每一步的最佳解是整体最优解的一部分。

判断是否适合贪心的标准

分析问题能否 分解为各步骤的局部最佳 ，并且这些局部最佳加起来是全局最佳。 检查问题是否具有 无后效性 ，即每一步的选择不会影响后续选择。 如果不满足这些条件（例如需要回溯、未来存在影响），通常考虑动态规划等其他算法。

二、贪心算法通俗举例

换零钱： 每次尽量选面值最大的钱币，逐步将金额减少到零。 区间选点问题： 总是选择终点最早的区间点，覆盖所有区间。

三、买卖股票的最佳时机II（LeetCode 122）

题目描述

给定一个股票价格数组，可以进行不限次数的购买和出售，但同一时间只能持有一只股票。问如何获得最大利润？

贪心解法核心思路

只要今天的价格比昨天高，就在昨天买入、今天卖出，赚取这段差价收益，最终所有上涨区间的利润累计就是最大收益。

profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit

这段代码只需一次遍历，效率非常高。

实例分析

[1,2,3,4,5]

：每次涨就卖一次，等同于一次买最低卖最高，总利润 4。

[7,1,5,3,6,4]

：把每一次正增长区间都累计起来，利润 4+3=7。

为什么后面的信息不影响当前决策？（无后效性证明）

决策只关心当前当天和下一天的价格变化—— 若

prices[i+1] > prices[i]

，立即卖出，赚取这个差价。 即使未来可能还有更高点，把所有连续上涨的差价相加，最终利润等于直接最低买最高卖。

数学表达

连续上涨区间累计所有小差值，与“最低买最高卖”结果完全一致。

(p2-p1) + (p3-p2) + ... + (pn-pn-1) = pn - p1

四、理论小结

用贪心算法解决股票买卖问题的前提是，每一次操作（买卖）只依赖当前局部信息。 贪心法总能覆盖所有正利润机会，无论区间如何波动，获得最大结果。 贪心法高效简洁，一步步积累当前最有利的决策即可取得全局最佳。