贪心算法详解

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。本文将从概念到实践，全面讲解贪心算法的思想、适用场景及常见题型。

---

一、什么是贪心算法？

1.1 贪心算法的定义

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。

核心思想：

• 局部最优：每一步都做出当前看起来最优的选择
• 全局最优：希望通过局部最优达到全局最优

通俗理解：

想象你在玩一个游戏，每一步都选择当前能获得的最高分数，不考虑未来的影响。

• 有时候这样能得到最高分（贪心适用）
• 有时候这样反而得不到最高分（贪心不适用）

---

1.2 贪心算法的特点

特点	说明
贪心选择性质	全局最优解可以通过局部最优选择达到
无后效性	当前选择不影响之前的选择，只影响未来
不可回溯	一旦做出选择，不能回退修改
高效性	通常时间复杂度较低，实现简单

---

1.3 贪心 vs 其他算法

算法	策略	特点
贪心算法	每步选局部最优	快，但不保证全局最优
动态规划	考虑所有子问题	慢，但保证全局最优
回溯算法	尝试所有可能，可回退	最慢，但能找到最优解
分治算法	分解子问题，合并结果	适用于可分解的问题

---

二、贪心算法的核心思想

2.1 贪心选择性质

定义： 一个问题的全局最优解可以通过一系列局部最优选择来达到。

关键问题：

• 如何证明贪心选择是正确的？
• 什么样的题目适合用贪心？

---

2.2 贪心算法的解题步骤

┌─────────────────────────────────────────────────────────────────┐
│                   贪心算法解题步骤                               │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  1. 建立数学模型                                                 │
│     └── 将问题抽象为数学问题                                     │
│                                                                 │
│  2. 确定贪心策略                                                 │
│     └── 确定每一步的局部最优选择标准                             │
│                                                                 │
│  3. 证明贪心选择性质                                             │
│     └── 证明局部最优能导致全局最优（或近似最优）                  │
│                                                                 │
│  4. 实现算法                                                     │
│     └── 按照贪心策略编写代码                                     │
│                                                                 │
│  5. 验证正确性                                                   │
│     └── 通过测试用例验证                                         │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

---

2.3 常见的贪心策略

策略	适用场景	示例
选择最大/最小	资源分配、区间问题	最多活动选择、最小硬币
选择最早结束	区间调度问题	最多不重叠区间
选择最早开始	区间覆盖问题	最少区间覆盖
按某种顺序排序后贪心	大多数贪心问题	分发饼干、跳跃游戏
优先队列（堆）	需要动态选择最优	合并 K 个有序链表

---

三、贪心算法的适用场景

3.1 什么情况下可以用贪心？

必须满足两个条件：

条件一：贪心选择性质

全局最优解可以通过局部最优选择达到。

示例：找零钱问题

• 硬币面额：1元、2元、5元
• 目标：凑出 11 元，使用最少硬币
• 贪心策略：每次选最大面额
  • 选 5 元 → 剩余 6 元
  • 选 5 元 → 剩余 1 元
  • 选 1 元 → 完成
  • 结果：3 枚硬币（最优）

条件二：最优子结构

问题的最优解包含子问题的最优解。

---

3.2 什么情况下不能用贪心？

示例：找零钱问题（特殊面额）

• 硬币面额：1元、3元、4元
• 目标：凑出 6 元
• 贪心策略：每次选最大面额
  • 选 4 元 → 剩余 2 元
  • 选 1 元 → 剩余 1 元
  • 选 1 元 → 完成
  • 结果：3 枚硬币
• 最优解：2 枚（3 + 3）

结论： 贪心不能保证全局最优，需要用动态规划。

---

3.3 贪心算法的经典应用场景

场景	说明	典型题目
区间调度	选择最多不重叠区间	活动选择问题
区间覆盖	用最小区间覆盖目标	跳跃游戏
资源分配	合理分配有限资源	分发饼干、任务调度
哈夫曼编码	数据压缩	构建最优前缀码
最小生成树	Prim、Kruskal 算法	图论问题
单源最短路径	Dijkstra 算法	图论问题

---

四、经典例题详解

4.1 例题一：分发饼干

题目：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例：

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

---

解法：

贪心策略：

• 为了满足更多的孩子，应该让胃口小的孩子先吃
• 用最小的饼干满足最小的胃口

步骤：

1. 对孩子胃口数组 g 排序（升序）
2. 对饼干尺寸数组 s 排序（升序）
3. 用双指针，尽量用最小的饼干满足当前孩子

代码实现：

function findContentChildren(g, s) {
  // 排序
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  
  let child = 0;  // 孩子的指针
  let cookie = 0; // 饼干的指针
  
  while (child < g.length && cookie < s.length) {
    if (s[cookie] >= g[child]) {
      // 当前饼干能满足当前孩子
      child++;  // 孩子被满足，看下一个孩子
    }
    // 无论是否满足，饼干都用掉了
    cookie++;
  }
  
  return child;  // 被满足的孩子数量
}

// 测试
console.log(findContentChildren([1, 2, 3], [1, 1])); // 1
console.log(findContentChildren([1, 2], [1, 2, 3])); // 2

时间复杂度： O(n log n) —— 主要是排序
空间复杂度： O(1) —— 只使用了常数额外空间

---

4.2 例题二：跳跃游戏

题目：
给定一个非负整数数组 nums，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例：

输入: nums = [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

输入: nums = [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。

---

解法一：贪心（从后向前）

贪心策略：

• 从后向前遍历，维护一个”能到达最后的位置”
• 如果当前位置能到达”目标位置”，则更新目标位置为当前位置

代码实现：

function canJump(nums) {
  let target = nums.length - 1;  // 目标位置（初始为最后一个位置）
  
  for (let i = nums.length - 2; i >= 0; i--) {
    // 如果当前位置能到达目标位置
    if (i + nums[i] >= target) {
      target = i;  // 更新目标位置为当前位置
    }
  }
  
  // 如果最后目标位置是 0，说明从起点可以到达
  return target === 0;
}

// 测试
console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // false

---

解法二：贪心（从前向后）

贪心策略：

• 维护当前能到达的最远位置
• 遍历过程中更新最远位置

代码实现：

function canJump(nums) {
  let maxReach = 0;  // 当前能到达的最远位置
  
  for (let i = 0; i < nums.length; i++) {
    // 如果当前位置超过了能到达的最远位置，说明无法到达
    if (i > maxReach) {
      return false;
    }
    
    // 更新最远能到达的位置
    maxReach = Math.max(maxReach, i + nums[i]);
    
    // 如果最远位置已经能到达或超过终点
    if (maxReach >= nums.length - 1) {
      return true;
    }
  }
  
  return true;
}

// 测试
console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // false

时间复杂度： O(n)
空间复杂度： O(1)

---

4.3 例题三：跳跃游戏 II

题目：
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例：

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

---

解法：

贪心策略：

• 在当前能跳的范围内，选择能跳得最远的那个位置
• 这样可以减少跳跃次数

代码实现：

function jump(nums) {
  let jumps = 0;      // 跳跃次数
  let currentEnd = 0; // 当前能到达的最远位置（当前跳跃的边界）
  let farthest = 0;   // 下一跳能到达的最远位置
  
  // 注意：最后一个位置不需要跳，所以遍历到倒数第二个
  for (let i = 0; i < nums.length - 1; i++) {
    // 更新下一跳能到达的最远位置
    farthest = Math.max(farthest, i + nums[i]);
    
    // 到达当前跳跃的边界
    if (i === currentEnd) {
      jumps++;           // 必须再跳一次
      currentEnd = farthest;  // 更新边界为下一跳的最远位置
      
      // 如果已经能到达终点，提前结束
      if (currentEnd >= nums.length - 1) {
        break;
      }
    }
  }
  
  return jumps;
}

// 测试
console.log(jump([2, 3, 1, 1, 4])); // 2
console.log(jump([2, 3, 0, 1, 4])); // 2
console.log(jump([1, 1, 1, 1, 1])); // 4

时间复杂度： O(n)
空间复杂度： O(1)

---

4.4 例题四：买卖股票的最佳时机 II

题目：
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例：

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

---

解法：

贪心策略：

• 只要今天的价格比昨天高，就在昨天买入今天卖出
• 这样可以获得所有上涨的利润

证明：

• 假设第 i 天买入，第 j 天卖出（i < j，prices[j] > prices[i]）
• 利润 = prices[j] - prices[i]
• = (prices[i+1] - prices[i]) + (prices[i+2] - prices[i+1]) + … + (prices[j] - prices[j-1])
• 所以每天上涨的利润加起来等于总利润

代码实现：

function maxProfit(prices) {
  let profit = 0;
  
  for (let i = 1; i < prices.length; i++) {
    // 如果今天比昨天高，就昨天买入今天卖出
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  
  return profit;
}

// 测试
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 7
console.log(maxProfit([1, 2, 3, 4, 5]));    // 4
console.log(maxProfit([7, 6, 4, 3, 1]));    // 0

时间复杂度： O(n)
空间复杂度： O(1)

---

4.5 例题五：根据身高重建队列

题目：
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例：

输入: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释:
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

---

解法：

贪心策略：

• 先按身高降序排序，身高相同则按 k 升序排序
• 然后依次插入，每个人插入到 k 指定的位置

为什么这样是对的？

• 先处理高的人，他们的位置不会受矮的人影响
• 矮的人插入到 k 位置，前面正好有 k 个高的人

代码实现：

function reconstructQueue(people) {
  // 按身高降序排序，身高相同则按 k 升序排序
  people.sort((a, b) => {
    if (a[0] !== b[0]) {
      return b[0] - a[0];  // 身高降序
    }
    return a[1] - b[1];     // k 升序
  });
  
  const result = [];
  
  // 依次插入到 k 指定的位置
  for (const person of people) {
    result.splice(person[1], 0, person);
  }
  
  return result;
}

// 测试
console.log(reconstructQueue([[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]));
// [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

时间复杂度： O(n²) —— 主要是 splice 操作
空间复杂度： O(n)

---

4.6 例题六：划分字母区间

题目：
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

返回一个表示每个字符串片段的长度的列表。

示例：

输入: s = "ababcbacadefegdehijhklij"
输出: [9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

---

解法：

贪心策略：

• 首先记录每个字母最后出现的位置
• 遍历字符串，维护当前片段的最远边界
• 当遍历位置等于最远边界时，可以划分

代码实现：

function partitionLabels(s) {
  // 记录每个字母最后出现的位置
  const lastIndex = new Map();
  for (let i = 0; i < s.length; i++) {
    lastIndex.set(s[i], i);
  }
  
  const result = [];
  let start = 0;  // 当前片段的起始位置
  let end = 0;    // 当前片段的最远边界
  
  for (let i = 0; i < s.length; i++) {
    // 更新当前片段的最远边界
    end = Math.max(end, lastIndex.get(s[i]));
    
    // 如果当前位置等于最远边界，可以划分
    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }
  
  return result;
}

// 测试
console.log(partitionLabels("ababcbacadefegdehijhklij")); // [9, 7, 8]
console.log(partitionLabels("eccbbbbdec")); // [10]

时间复杂度： O(n)
空间复杂度： O(1) —— 最多 26 个字母

---

4.7 例题七：合并区间

题目：
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例：

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

---

解法：

贪心策略：

• 按区间左端点排序
• 遍历区间，如果当前区间与上一个合并后的区间重叠，则合并
• 否则，将当前区间加入结果

代码实现：

function merge(intervals) {
  if (intervals.length <= 1) return intervals;
  
  // 按区间左端点排序
  intervals.sort((a, b) => a[0] - b[0]);
  
  const result = [intervals[0]];
  
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = result[result.length - 1];
    
    // 如果当前区间与上一个区间重叠
    if (current[0] <= last[1]) {
      // 合并区间，更新右端点
      last[1] = Math.max(last[1], current[1]);
    } else {
      // 不重叠，加入结果
      result.push(current);
    }
  }
  
  return result;
}

// 测试
console.log(merge([[1,3],[2,6],[8,10],[15,18]])); // [[1,6],[8,10],[15,18]]
console.log(merge([[1,4],[4,5]])); // [[1,5]]
console.log(merge([[1,4],[0,4]])); // [[0,4]]

时间复杂度： O(n log n) —— 主要是排序
空间复杂度： O(n)

---

五、贪心算法 vs 动态规划

5.1 核心区别

特性	贪心算法	动态规划
选择策略	每步选局部最优	考虑所有可能，选全局最优
时间复杂度	通常 O(n) 或 O(n log n)	通常 O(n²) 或更高
空间复杂度	通常 O(1)	通常 O(n) 或更高
正确性保证	不一定全局最优	一定全局最优
适用场景	具有贪心选择性质的问题	具有最优子结构的问题
典型问题	区间调度、跳跃游戏	背包问题、最长子序列

---

5.2 如何区分用贪心还是动态规划？

方法一：举反例

尝试找一个反例，证明贪心不能得到最优解。

示例：找零钱

• 硬币：1, 3, 4
• 目标：6
• 贪心：4 + 1 + 1 = 3 枚
• 最优：3 + 3 = 2 枚
• 结论： 不能用贪心，用动态规划

---

方法二：问题特征

特征	适合贪心	适合动态规划
选择后不影响其他选择	✅	❌
需要记录历史状态	❌	✅
需要比较所有子问题	❌	✅
局部最优能导致全局最优	✅	不一定

---

方法三：经典问题对照

问题	贪心	动态规划
活动选择问题	✅	✅
背包问题	❌（分数背包可以）	✅
最长递增子序列	❌	✅
跳跃游戏	✅	✅
股票买卖 II	✅	✅
股票买卖 I	❌	✅

---

5.3 对比示例

示例一：活动选择问题

问题： 选择最多不重叠的活动。

贪心解法：

function maxActivities(activities) {
  // 按结束时间排序
  activities.sort((a, b) => a[1] - b[1]);
  
  let count = 1;
  let lastEnd = activities[0][1];
  
  for (let i = 1; i < activities.length; i++) {
    if (activities[i][0] >= lastEnd) {
      count++;
      lastEnd = activities[i][1];
    }
  }
  
  return count;
}

贪心策略： 每次选结束时间最早的
正确性： 可以证明贪心选择性质成立

---

示例二：0-1 背包问题

问题： 物品不可分割，求最大价值。

贪心尝试： 每次选价值密度（价值/重量）最高的

反例：

背包容量：50
物品1：重量 10，价值 60（密度 6）
物品2：重量 20，价值 100（密度 5）
物品3：重量 30，价值 120（密度 4）

贪心：选物品1 → 剩余 40，再选物品2 → 总价值 160
最优：选物品2 + 物品3 → 总价值 220

结论： 必须用动态规划

---

六、贪心算法的题型分类

6.1 按问题类型分类

类型一：区间问题

特点： 涉及时间区间或范围的处理

题目	策略
合并区间	按左端点排序，重叠则合并
插入区间	找到插入位置，合并重叠区间
用最少数量的箭引爆气球	按右端点排序，贪心选择
无重叠区间	按结束时间排序，选择最多

---

类型二：分配问题

特点： 资源分配，满足尽可能多的需求

题目	策略
分发饼干	排序后，小饼干满足小胃口
根据身高重建队列	高个子先排，矮个子插入
任务调度器	计算冷却时间，贪心填充

---

类型三：序列问题

特点： 对序列进行操作，达到某种目标

题目	策略
跳跃游戏	维护最远可达位置
买卖股票 II	收集所有上涨利润
划分字母区间	记录最后位置，贪心划分

---

类型四：构造问题

特点： 构造满足条件的数据结构

题目	策略
重构字符串	按频率排序，交替放置
reorganize string	最大堆，每次选频率最高的

---

6.2 按贪心策略分类

策略	适用场景	示例
排序后贪心	大多数贪心问题	分发饼干、合并区间
双指针	两个数组/序列	分发饼干、盛最多水
维护最值	需要动态更新最优	跳跃游戏、股票买卖
优先队列	每次选最优	重构字符串、合并 K 个链表
区间处理	区间相关	合并区间、活动选择

---

七、常见面试题总结

7.1 必须掌握的面试题

题目	难度	类型
分发饼干	简单	分配问题
买卖股票的最佳时机 II	简单	序列问题
跳跃游戏	中等	序列问题
跳跃游戏 II	中等	序列问题
合并区间	中等	区间问题
根据身高重建队列	中等	构造问题
划分字母区间	中等	序列问题
无重叠区间	中等	区间问题
用最少数量的箭引爆气球	中等	区间问题
任务调度器	中等	分配问题

---

7.2 面试回答要点

Q：什么是贪心算法？

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。它的核心特点是贪心选择性质和无后效性。

Q：贪心算法和动态规划的区别？

• 贪心：每步选局部最优，效率高但不保证全局最优
• 动态规划：考虑所有子问题，一定能得到全局最优，但效率较低

Q：如何判断一个问题能否用贪心？

1. 尝试举反例，看贪心是否能得到最优解
2. 检查是否具有贪心选择性质
3. 检查是否具有最优子结构
4. 参考经典问题，看是否属于贪心适用类型

Q：贪心算法的优缺点？

优点： 实现简单、时间复杂度低、代码简洁
缺点： 不一定得到全局最优、需要证明正确性

---

八、总结

8.1 贪心算法核心要点

要点	内容
核心思想	每步选局部最优，希望达到全局最优
关键性质	贪心选择性质、无后效性
解题步骤	建立模型 → 确定策略 → 证明正确性 → 实现
常见策略	排序后贪心、双指针、维护最值、优先队列
适用场景	区间问题、分配问题、序列问题

8.2 贪心 vs 动态规划决策树

遇到问题
    │
    ├── 是否能举出反例？
    │   ├── 能 → 用动态规划
    │   └── 不能 → 继续
    │
    ├── 是否具有贪心选择性质？
    │   ├── 否 → 用动态规划
    │   └── 是 → 继续
    │
    ├── 局部最优能导致全局最优？
    │   ├── 能 → 用贪心算法 ✅
    │   └── 不能确定 → 尝试证明或对比两种方法
    │

8.3 学习建议

1. 理解核心思想：局部最优 → 全局最优
2. 掌握经典题目：分发饼干、跳跃游戏、合并区间
3. 学会证明：能简单证明贪心选择的正确性
4. 对比学习：与动态规划对比，理解适用场景
5. 多做练习：贪心题目套路明显，多练就能掌握

贪心算法是算法面试中的常客，虽然实现简单，但关键在于判断是否能用贪心。记住：贪心选择性质是核心，举反例是检验方法！