贪心算法在技术面试中的实战精要：从识别到破解的五大高频场景

如果你正在准备技术面试，尤其是那些以算法考察著称的大厂，那么“贪心算法”这个词一定不会陌生。它不像动态规划那样需要复杂的状态推导，也不像回溯那样需要遍历所有可能，但恰恰是这种“目光短浅”的局部最优选择，却能在特定问题上展现出惊人的简洁与高效。然而，面试中最棘手的往往不是写出贪心算法的代码，而是如何在一道陌生的题目面前，快速判断它是否适用于贪心策略，以及如何设计出正确的贪心选择标准。

这篇文章，我将结合自己刷题和面试的经验，为你拆解LeetCode上五个最经典、最高频的贪心算法应用场景。我不会仅仅给出答案，而是会深入剖析每道题背后的“贪心思想”是如何被发掘和证明的，并对比不同解法的优劣，帮你建立起一套快速识别和解决贪心问题的思维框架。无论你是正在刷题冲刺的应届生，还是希望巩固算法基础的在职工程师，相信都能从中获得启发。

1. 贪心算法的本质与面试识别要诀

在深入具体题目之前，我们必须先统一思想：贪心算法到底是什么，以及面试官为什么爱考它？

贪心算法的核心思想，是在每一步都做出当前看来最优的选择，并期望通过这一系列局部最优选择，最终导向全局最优解。这听起来很像我们日常生活中“走一步看一步”的决策方式，但关键在于，它要求问题必须具备两个关键性质：

1. 贪心选择性质：每一步的局部最优选择，能保证最终得到全局最优解。这个选择一旦做出，就不可回退。
2. 最优子结构：问题的最优解包含其子问题的最优解。

在面试的紧张环境下，如何快速判断一个问题是否具备这些性质呢？我总结了几个常见的“信号”：

• 关键词：题目中经常出现“最大/最小数量”、“最大/最小长度”、“最短/最长时间”、“能否到达/完成”等优化目标。
• 排序预处理：很多贪心问题在决策前，都需要对输入数据（如区间、任务、数字）按照某种规则（如结束时间、开始时间、权重、数值大小）进行排序。这是一个强烈的提示。
• 无后效性：当前的选择不会影响后续子问题的结构。这是贪心与动态规划（DP）的一个核心区别。DP的子问题间有重叠和相互影响，而贪心的子问题通常是独立的。

注意：贪心算法不能保证对所有问题都得到最优解。面试中，如果你提出用贪心，必须心中有数，要么你能给出严谨的证明（或至少是直观的论证），要么你明确知道这只是一个近似解法并说明原因。

为了更清晰地对比贪心与动态规划，我们看下面这个表格：

特性	贪心算法	动态规划
决策方式	每步做出不可回退的局部最优选择	每步基于之前所有状态做出选择，可回退（通过状态转移）
子问题	通常独立，选择后规模减小	子问题重叠，需保存中间结果
时间复杂度	通常较低，O(n log n) 或 O(n) 常见	通常较高，O(n^2) 或带状态压缩
证明要求	高，需证明局部最优能导致全局最优	相对较低，重点在状态定义和转移方程的正确性
典型问题	区间调度、跳跃游戏、分糖果	背包问题、最长公共子序列、股票买卖系列

理解这张表格，能帮助你在面对问题时做出初步的算法选择。

2. 场景一：区间调度与合并——在有限时间内做最多的事

这是贪心算法最直观、最经典的应用场景。LeetCode上相关的题目有56. 合并区间和435. 无重叠区间。这类问题的核心是：给你若干个时间区间，你如何安排才能完成最多不重叠的任务，或者如何合并所有重叠的区间？

贪心策略：优先选择结束时间最早的区间。

为什么是结束时间最早，而不是开始时间最早或持续时间最短？我们可以这样思考：一个区间结束得越早，给后续区间留出的时间就越多，选择后续区间的机会也就越大。这是一种典型的“为未来创造更多可能”的贪心思想。

以435. 无重叠区间为例，题目要求移除最少数量的区间，使得剩下的区间互不重叠。这等价于选择最多数量的互不重叠区间。

操作步骤：

1. 将所有区间按照结束时间进行升序排序。
2. 初始化一个变量end记录当前已选区间的结束时间，初始为负无穷（或第一个区间的结束时间），计数器count记录选择的区间数。
3. 遍历排序后的区间：
   • 如果当前区间的开始时间 >= end，说明它与已选区间不冲突，我们可以选择它。更新end为当前区间的结束时间，count加1。
   • 否则，说明当前区间与已选区间冲突，跳过它（相当于移除）。
4. 最终，总区间数 - count就是最少需要移除的区间数。

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(n log n)：主要开销在于排序。
• 空间复杂度 O(1) 或 O(log n)：取决于排序算法的空间开销。

面试延伸：面试官可能会问，如果按开始时间排序行不行？你可以构造反例：[[1, 100], [2, 3], [4, 5]]，按开始时间排序会选择第一个区间，从而错过后面两个更优的区间。这恰恰证明了贪心策略选择正确标准的重要性。

3. 场景二：跳跃游戏——判断与计算最小步数

LeetCode上55. 跳跃游戏和45. 跳跃游戏 II是贪心算法的另一个招牌问题。它模拟了一个从数组起点开始，根据每个位置的值（最大跳跃长度）决定能否到达终点或最少需要多少步到达终点。

贪心策略：维护一个“当前能到达的最远位置”。

对于55. 跳跃游戏（判断能否到达），我们不需要知道具体怎么跳，只需要关心最远能覆盖到哪里。

操作步骤：

1. 初始化farthest = 0，表示从起点开始能到达的最远索引。
2. 遍历数组的每个索引i：
   • 如果 i > farthest，说明当前位置已经超出了之前所有跳跃能到达的范围，即无法到达i，直接返回False。
   • 否则，更新 farthest = max(farthest, i + nums[i])。
3. 如果遍历结束，说明最远距离可以覆盖最后一个位置，返回True。

def canJump(nums):
    farthest = 0
    for i in range(len(nums)):
        if i > farthest: # 无法到达当前位置
            return False
        farthest = max(farthest, i + nums[i])
        if farthest >= len(nums) - 1: # 提前终止
            return True
    return farthest >= len(nums) - 1

对于45. 跳跃游戏 II（求最小跳跃次数），策略需要稍作调整：我们需要在可到达的范围内，选择下一次能跳得最远的点作为起跳点。

操作步骤：

1. 初始化jumps = 0（跳跃次数），current_end = 0（当前跳跃能到达的边界），farthest = 0（在current_end范围内能跳到的最远位置）。
2. 遍历数组（注意，不需要遍历最后一个元素，因为到达最后位置后不需要再跳）：
   • 不断更新 farthest = max(farthest, i + nums[i])。
   • 当 i == current_end 时，说明已经到达当前跳跃的边界，必须进行一次新的跳跃。jumps += 1，并将current_end更新为farthest。
3. 返回jumps。

def jump(nums):
    n = len(nums)
    if n <= 1:
        return 0
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(n - 1): # 不需要在最后一个位置起跳
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
            if current_end >= n - 1:
                break
    return jumps

复杂度分析：两种方法都是**O(n)的时间复杂度和O(1)**的空间复杂度，效率非常高。

面试点睛：这道题是考察你是否理解贪心“阶段性推进”思想的绝佳例子。它不像DP那样需要维护一个dp[i]数组来记录到达每个位置的最小步数，而是通过维护几个关键变量，在遍历过程中就完成了决策。

4. 场景三：分发糖果与队列重建——满足双向约束

135. 分发糖果和406. 根据身高重建队列这类问题，其贪心策略往往需要多步处理或排序，以满足多个维度的约束条件。

以135. 分发糖果为例，规则是：每个孩子至少一个糖；相邻孩子中评分高的必须获得更多糖果。这形成了一个双向的约束链。

贪心策略：两次遍历，分别处理左规则和右规则。

1. 从左到右遍历：只关心右边孩子评分比左边高的情况。如果ratings[i] > ratings[i-1]，那么candy[i] = candy[i-1] + 1。
2. 从右到左遍历：只关心左边孩子评分比右边高的情况。如果ratings[i] > ratings[i+1]，那么candy[i]应该是max(candy[i], candy[i+1] + 1)（要同时满足从左到右的规则）。

def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    # 从左到右
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    # 从右到左
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
    return sum(candies)

对于406. 根据身高重建队列，每个人由(h, k)表示，h是身高，k是前面身高大于等于他的人数。这看起来有点绕。

贪心策略：先按身高降序、同身高按k值升序排序，再按k值插入。

1. 排序：people.sort(key=lambda x: (-x[0], x[1]))。这样，身高最高的人排前面，对于身高相同的人，k小的（前面人少的）排前面。
2. 插入：新建一个空列表result。遍历排序后的人，根据他的k值，将其插入到result列表的索引k的位置。

为什么这样做？因为身高高的人看不见身高低的人，所以先把身高高的人按他们的k值放好，后面插入矮个子时，不会影响已经排好的高个子的k值（因为矮个子排在他们前面或后面都不影响“前面身高>=他的人”这个计数）。

def reconstructQueue(people):
    people.sort(key=lambda x: (-x[0], x[1]))
    result = []
    for p in people:
        result.insert(p[1], p) # 在索引k处插入
    return result

复杂度分析：分发糖果是O(n)，重建队列排序是O(n log n)，但插入操作在列表中为O(n)，总复杂度为O(n²)。可以使用链表优化插入，但Python列表的插入在数据量不大时尚可接受。面试时需要指出这一点。

5. 场景四：任务调度器与重构字符串——巧用“桶”思想

621. 任务调度器和767. 重构字符串是贪心结合“桶排序”思想的典型。它们都需要在满足特定间隔要求的前提下，安排任务或字符。

以621. 任务调度器为例，给定一个任务列表和冷却时间n，相同任务之间必须间隔至少n个单位时间，求完成所有任务的最短时间。

贪心策略：优先安排出现次数最多的任务。

1. 统计每个任务的频率，找到出现次数最多的任务，设其频率为max_freq。
2. 假设有count个任务都出现了max_freq次。
3. 我们可以想象把出现最多次的任务作为框架。完成所有max_freq次的任务，至少需要 (max_freq - 1) * (n + 1) + count 个时间单位。第一部分是框架，第二部分是最后一轮的任务。
4. 但是，如果任务种类很多，冷却时间n很小，可能框架之间的空位不足以放下所有其他任务。此时，实际所需时间就是任务总数len(tasks)。

def leastInterval(tasks, n):
    freq = [0] * 26
    for t in tasks:
        freq[ord(t) - ord('A')] += 1
    freq.sort()
    max_freq = freq[-1]
    count = freq.count(max_freq) # 有多少个任务具有最大频率
    
    # 公式计算 vs 任务总数
    return max(len(tasks), (max_freq - 1) * (n + 1) + count)

面试深度：这道题的难点在于公式的推导和理解。面试时，你可以通过画图（用最多任务作为“桶”的边界）来直观解释。关键在于理解，最短时间由任务数量和由最频繁任务决定的框架长度两者中的较大者决定。

6. 场景五：加油站与最大子数组——局部与全局的权衡

134. 加油站和53. 最大子数组和（Kadane算法）展示了贪心算法如何解决环形数组和连续子数组的极值问题。

134. 加油站是一个环形路线问题，汽车从某个加油站出发，需要绕一圈回来。每个加油站有油量gas[i]，到下一站耗油cost[i]。

贪心策略：如果总油量>=总耗油，则一定有解。且起点可以从局部累加油量最低点的下一个站开始。 更精确的贪心解法是：

1. 初始化total_tank和curr_tank为0，start_station为0。
2. 遍历每个加油站i：
   • total_tank += gas[i] - cost[i]
   • curr_tank += gas[i] - cost[i]
   • 如果curr_tank < 0，说明从start_station到i不可行。那么将起点设为i+1，并重置curr_tank = 0。
3. 遍历结束后，如果total_tank >= 0，则start_station就是答案，否则返回-1。

def canCompleteCircuit(gas, cost):
    total_tank, curr_tank, start = 0, 0, 0
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        curr_tank += gas[i] - cost[i]
        if curr_tank < 0:
            start = i + 1
            curr_tank = 0
    return start if total_tank >= 0 else -1

这个算法的精妙之处在于，它利用了“如果从A点无法到达B点，那么A、B之间的任何点作为起点都无法到达B点”这一性质，从而一次性找到可能的起点。

53. 最大子数组和的Kadane算法则是贪心的另一个典范：当连续子数组的和变为负数时，它对于后续子数组的和只会有负面影响，因此应该被舍弃，从下一个元素重新开始计算。

def maxSubArray(nums):
    curr_sum = max_sum = nums[0]
    for num in nums[1:]:
        curr_sum = max(num, curr_sum + num) # 关键：要么从当前元素重新开始，要么继续累加
        max_sum = max(max_sum, curr_sum)
    return max_sum

复杂度：两者都是**O(n)**时间，**O(1)**空间，是这类问题的最优解法。

在实际面试中，遇到数组、区间、调度类的问题，不妨先想想排序后贪心是否可行。多练习这几类经典问题，培养对贪心策略的“嗅觉”，比死记硬背模板要有效得多。我自己的经验是，把每道贪心题为什么这么“贪”的原理想明白，比刷十道题都管用。下次再遇到新题，你就能更快地抓住那个“局部最优”的关键点了。