贪心算法实战：分发糖果与区间问题解析-平芜编程栈

1. 贪心算法核心思想回顾

在进入具体问题之前，我们先明确贪心算法的基本特征。这种算法在每一步选择中都采取当前状态下最优的决策，希望通过局部最优解的累积达到全局最优。与动态规划不同，贪心算法不会回退，这也决定了它并非适用于所有问题场景。

贪心算法有效的三个关键前提条件：

贪心选择性质：局部最优解能导致全局最优解
最优子结构：问题的最优解包含子问题的最优解
无后效性：某个状态以前的过程不会影响后续决策

注意：实际应用中需要严格证明问题满足这些条件，否则可能得到错误结果。很多初学者容易忽略这一点。

2. 分发糖果问题解析

2.1 问题描述与建模

假设有N个孩子排成一列，每个孩子有一个评分值。要求：

每个孩子至少分到1颗糖
评分更高的孩子必须比相邻孩子获得更多糖果
求最少需要准备的糖果总数

这个问题可以抽象为在满足相邻约束条件下，寻找一个非负整数序列的最小和。关键在于如何处理相邻比较产生的矛盾约束。

2.2 双向遍历解法

最有效的解法是进行两次独立遍历：

从左向右遍历：确保右边高分孩子比左边多

def candy(ratings): n = len(ratings) left = [1] * n for i in range(1, n): if ratings[i] > ratings[i-1]: left[i] = left[i-1] + 1

从右向左遍历：确保左边高分孩子比右边多

right = [1] * n for i in range(n-2, -1, -1): if ratings[i] > ratings[i+1]: right[i] = right[i+1] + 1 return sum(max(left[i], right[i]) for i in range(n))

时间复杂度O(n)，空间复杂度O(n)。这种双向处理巧妙地解决了单向遍历无法兼顾两边约束的问题。

2.3 常数空间优化

实际上可以优化到O(1)空间：

def candy(ratings): n = len(ratings) res = 1 inc, dec, pre = 1, 0, 1 for i in range(1, n): if ratings[i] >= ratings[i-1]: dec = 0 pre = (1 if ratings[i] == ratings[i-1] else pre + 1) res += pre inc = pre else: dec += 1 if dec == inc: dec += 1 res += dec pre = 1 return res

这个优化版本通过记录当前递增/递减序列长度来动态计算糖果数，适合处理大规模数据。

3. 无重叠区间问题

3.1 问题转化思路

给定一组区间，要求移除最少数量的区间使剩余区间互不重叠。这可以转化为选择最多不重叠区间的问题，是典型的区间调度问题。

关键思路：按照结束时间排序，优先选择结束早的区间，为后续选择留出更多空间。

3.2 贪心策略实现

def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(key=lambda x: x[1]) count = 1 end = intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] >= end: count += 1 end = intervals[i][1] return len(intervals) - count

时间复杂度主要来自排序的O(nlogn)。这种策略的正确性基于：选择结束最早的区间可以为后续留下最大的选择空间。

3.3 不同排序方式的对比

实践中也可以尝试按开始时间排序：

intervals.sort(key=lambda x: x[0]) end = intervals[0][1] count = 1 for i in range(1, len(intervals)): if intervals[i][0] >= end: count += 1 end = intervals[i][1] else: end = min(end, intervals[i][1])

这种实现需要更复杂的end值维护，但同样有效。两种方法在不同场景下各有优势。

4. 合并区间问题

4.1 问题特征分析

给定一组可能重叠的区间，合并所有重叠的区间。这与前一个问题形成对比，需要处理的是重叠而非分离。

关键观察：排序后可以线性时间完成合并，因为重叠区间必然连续。

4.2 标准解法实现

def merge(intervals): intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: if not merged or merged[-1][1] < interval[0]: merged.append(interval) else: merged[-1][1] = max(merged[-1][1], interval[1]) return merged

时间复杂度O(nlogn)，主要来自排序步骤。空间复杂度O(n)用于存储结果。