贪心选择 (Greedy Choice)

---

核心算法思想：贪心选择 (Greedy Choice)

贪心算法的本质是在对问题求解时，每一步都做出在当前看来是最好的选择，期望通过一系列局部最优解，最终导出全局最优解。

• 成立前提 (Greedy Choice Property & Optimal Substructure):

  1. 贪心选择性质：一个全局最优解可以通过局部最优选择（贪心选择）来达到。这是贪心算法与动态规划的关键区别，后者会保留所有可能的局部选择。
  2. 最优子结构：问题的最优解包含了其子问题的最优解。

• 实现范式:

  通常遵循 排序 -> 遍历 -> 决策 的模式。排序是为了创造一个有序的环境，使得局部最优决策的实施变得简单和直接。

---

---

模型一：区间调度与区间合并 (Interval Scheduling & Merging)

该模型处理一系列区间，目标是选择不重叠的子集或合并重叠的区间。

核心原理

通过对区间的某个端点（通常是左端点或右端点）进行排序，将问题转化为线性扫描。决策的关键在于，当出现重叠时，保留哪个区间能为后续选择留下最大的可能性。

经典例题 1：无重叠区间 (LeetCode 435)

1. 问题定义

• 目标: 给定区间集合，计算最少需要移除多少个区间，才能使剩余区间互不重叠。
• 转换: 此问题等价于“寻找最多数量的互不重叠区间”。移除数量 = 总数量 - 最大不重叠数量。

2. 贪心策略解构

• 定义: 保留尽可能多的不重叠区间。

• 实现

  :

  1. 排序: 将所有区间按 左端点 从小到大排序。
  2. 决策: 遍历排序后的区间。当两个区间i和j重叠时（i在前），必须移除一个。为了给后续区间留出更多空间，应当移除 右端点更大 的那个区间。这等效于保留右端点更小的区间。

• 约束: 排序是贪心策略得以实施的前提。保留结束早的区间，是局部最优选择。

**3. C++ 实现 **

#include <iostream>
#include <vector>
#include <algorithm>// LeetCode 435: Non-overlapping Intervals
class Solution {
public:int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {if (intervals.empty()) {return 0;}// 1. 按左端点排序// C++ STL sort默认对vector<int>按字典序排序，即先比较第一个元素std::sort(intervals.begin(), intervals.end());int removed_count = 0;// right_boundary 记录当前已保留区间的最小右边界int right_boundary = intervals[0][1]; // 2. 遍历决策for (int i = 1; i < intervals.size(); ++i) {// 3. 检查重叠if (intervals[i][0] < right_boundary) {// 出现重叠，必须移除一个removed_count++;// 贪心选择：保留右端点更小的那个区间// 这样可以为后续区间留出更多空间right_boundary = std::min(right_boundary, intervals[i][1]);} else {// 没有重叠，更新右边界right_boundary = intervals[i][1];}}return removed_count;}
};

---

模型二：自定义排序贪心 (Greedy with Custom Sorting)

此类问题的贪心策略体现在一个非标准的排序规则上。一旦找到正确的排序规则，问题即迎刃而解。

核心原理

通过定义一个特殊的比较函数 compare(a, b)，使得元素按此规则排序后，直接拼接或处理就能得到全局最优解。证明该比较规则的有效性（尤其是传递性）是关键。

经典例题 2：最大数 (LeetCode 179)

1. 问题定义

• 目标: 将一组非负整数重新排列，组成一个最大的整数。

2. 贪心策略解构

• 定义: 找到一种排列顺序，使得拼接后的数值最大。
• 实现: 对于任意两个数 a 和 b，如果拼接结果 a + b > b + a，那么在最终结果中 a 必须排在 b 的前面。
• 约束: 此贪心策略的正确性依赖于该排序规则的传递性。即，若 a > b 且 b > c，则必须 a > c。此性质对于字符串拼接构成的序关系成立。

**3. C++ 实现 **

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>// LeetCode 179: Largest Number
class Solution {
public:std::string largestNumber(std::vector<int>& nums) {// 1. 将所有数字转换为字符串std::vector<std::string> strs;for (int num : nums) {strs.push_back(std::to_string(num));}// 2. 自定义排序规则std::sort(strs.begin(), strs.end(), [](const std::string& s1, const std::string& s2) {return s1 + s2 > s2 + s1;});// 3. 拼接结果std::string result;for (const std::string& s : strs) {result += s;}// 4. 处理前导零的特殊情况 (例如输入是 [0, 0])if (result[0] == '0') {return "0";}return result;}
};

---

模型三：序列决策与状态跃迁 (Sequence Decision & State Transition)

在序列上做决策，每一步的选择会影响后续状态。贪心策略通常是选择能使下个状态最优（如跳得最远）的选项。

核心原理

将问题看作在序列上的一个或多个“回合”。在每个回合内，做出一个贪心选择，以确定下一个回合的起始状态。这常被类比为广度优先搜索（BFS）的“层序遍历”。

经典例题 3：跳跃游戏 II (LeetCode 45)

1. 问题定义

• 目标: 给定一个数组，每个元素代表从此位置可跳跃的最大长度，求跳到数组末尾所需的最少步数。

2. 贪心策略解构

• 定义: 在每一步（每一“层”）可达的范围内，找到一个能让“下一步”跳得最远的位置。

• 实现

  :

  1. current_end: 当前这一步能到达的最远边界。
  2. next_max_pos: 从 [0, current_end] 区间内所有位置出发，下一步能到达的最远位置。
  3. steps: 跳跃步数。
  4. 遍历数组，在到达 current_end 之前，持续更新 next_max_pos。当遍历到 current_end 时，意味着这一步必须跳了，步数 steps 加一，同时将 current_end 更新为 next_max_pos。

• 约束: 题目保证总能到达终点。该策略在每一步都选择“最大化未来收益”（跳得更远），是典型的贪心思想。

**3. C++ 实现 **

#include <iostream>
#include <vector>
#include <algorithm>// LeetCode 45: Jump Game II
class Solution {
public:int jump(std::vector<int>& nums) {int n = nums.size();if (n <= 1) return 0;int steps = 0;// 当前步数能覆盖的最远位置int current_end = 0;// 在当前覆盖范围内，下一步能跳到的最远位置int next_max_pos = 0;for (int i = 0; i < n - 1; ++i) {// 1. 更新下一步能跳到的最远位置next_max_pos = std::max(next_max_pos, i + nums[i]);// 2. 到达当前步数的边界，必须进行下一次跳跃if (i == current_end) {steps++;current_end = next_max_pos;// 优化：如果下一步已经能覆盖终点，可提前返回if (current_end >= n - 1) {return steps;}}}return steps;}
};

---

模型四：反向思考与贡献度计算 (Reverse Thinking & Contribution Calculation)

部分问题正向思考路径复杂，但逆向思考或从贡献度角度分析，贪心策略会变得显而易见。

核心原理

• 正难则反: 如果从 start 到 target 的操作复杂，尝试从 target 到 start，看操作是否会变得唯一或更简单。
• 贡献度分析: 不模拟过程，而是计算每个元素的净贡献（如 gas[i] - cost[i]），并基于贡献度进行决策。

经典例题 4：加油站 (LeetCode 134)

1. 问题定义

• 目标: 环形路线上有N个加油站，gas[i]是第i站的油量，cost[i]是到下一站的油耗。找出一个起点，使得汽车能绕行一周。

2. 贪心策略解构

• 定义: 找到一个可行的起点。

• 实现 (关键洞察)

  :

  1. 如果 sum(gas) < sum(cost)，则总油量不足以支付总油耗，绝不可能跑完一圈，直接返回 -1。
  2. 如果从 i 点出发，在 j 点“趴窝”（油量为负），则从 i 到 j 之间的任何一个点出发，都无法越过 j 点。
  3. 基于此，当从 start 点出发，累积油量 total_tank 变为负数时，说明 [start, current_i] 区间内所有点都不能作为起点。下一个可能的起点就是 current_i + 1。

• 约束: 题目保证解唯一。利用这个贪心策略，我们只需一次线性扫描即可找到答案。

• C++ 实现 (CodeMaster 优化)

#include <iostream>
#include <vector>
#include <numeric>// LeetCode 134: Gas Station
class Solution {
public:int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {int n = gas.size();// 关键洞察 1: 检查总油量是否足够int total_diff = 0;// 当前油箱的油量int current_tank = 0;// 起始点int start_station = 0;for (int i = 0; i < n; ++i) {int diff = gas[i] - cost[i];total_diff += diff;current_tank += diff;// 关键洞察 2: 如果当前油箱为负，则[start_station, i]都不能作为起点if (current_tank < 0) {// 将下一个位置作为新的候选起点start_station = i + 1;// 重置当前油箱current_tank = 0;}}// 如果总油量差大于等于0，则一定存在解，且该解就是 start_station// 否则无解return (total_diff >= 0) ? start_station : -1;}
};

---