企业官网建设流程全解析

刷题刷到第27天，终于轮到了贪心算法。说实话，之前我对贪心一直有点“偏见”，总觉得它不像动态规划、回溯那样有清晰的框架，每道题像是灵光一现，很难系统化。但真正刷完一批经典题目之后，我发现贪心其实也有迹可循，它考验的不是模板记忆，而是对“局部最优能不能推出全局最优”的判断力。今天这篇就把我这段时间啃贪心的完整路径整理出来：核心思路、经典题型、实战技巧、常见坑，一次讲透。

贪心算法（Greedy Algorithm）解决什么问题，一句话概括：每一步决策都取当前看起来最好的选择，希望最终累积出全局最优。它的典型应用场景包括资源分配、区间调度、跳跃类问题、求最大最小值问题。这篇文章适合三类人：准备笔试面试的求职者、算法刚入门想建立题型体系的新手、以及在贪心和动态规划之间经常选错方向的同学。只要你正卡在“这题我该不该用贪心”的纠结里，这篇就是为你写的。

1. 贪心算法到底在贪什么：核心思路与适用范围

1.1 局部最优到全局最优：贪心的底层逻辑

贪心的决策过程有一个鲜明特征：只看现在，不看未来。走到某一步时，当前状态有哪些可选方案，直接选那个在当下看起来最优的，然后往下走，绝不回头。这和现实里的“走一步看一步”很像，比如你逛超市想买最划算的组合，但又不允许反复比较所有搭配时，就只能在每个货架前选最顺眼的商品。

但这里有一个容易误解的地方：贪心并不保证一定得到全局最优。它只在某些特定结构的问题里成立。比如找零钱问题，如果用1、5、10、20这些面额，每次优先找最大面额，最后一定是最少张数；可如果货币面额改成1、5、11，同样是找15块，贪心会先拿11，再拿4个1，一共5张，而最优解是3张5块。这就是经典的贪心失败反例。

所以在学习贪心时，我的建议是先别急着背题型，而是要把这句话刻在脑子里：贪心不是“一种算法模板”，而是一种“问题性质”。只有当问题的结构保证每一步的局部最优能拼出全局最优时，贪心才是正确解法。后续所有题目的分析，本质上都是在回答“这个性质到底存不存在”。

1.2 什么时候才敢用贪心：两个必要条件

判断一道题能不能用贪心，理论上需要满足两个条件：贪心选择性质和最优子结构。

贪心选择性质指的是，通过一系列局部最优选择，能最终拼出全局最优解。说得直白一点，就是你在每一步做的“最划算选择”，永远不阻碍后面拿到更好的结果。最优子结构则是指，整个问题的最优解，包含了子问题的最优解。这两个条件听起来抽象，但实际操作中我们可以用一种更接地气的方式去判断：先别管证明，直接手推三到五个测试用例，如果每一步贪心策略在这些用例里都正确，而且你举不出反例，那就可以大胆写。写完之后再回头想想证明，如果实在想不出来，再去找题解看别人的证明逻辑。

这里我额外补充一张对比表格，帮你彻底区分贪心和动态规划，因为太多人在这两者之间摇摆不定。

这张表是我每次刷题前都会在脑子里过一遍的。遇到一个题目，先想它是“一条路走下去”还是“有多条路要比较”，往往答案就清晰了一半。

1.3 贪心的天敌：哪些场景不能碰

贪心最大的天敌就是“需要全局统筹”的问题，最典型的就是0-1背包。每个物品有重量和价值，背包容量有限，目标是装下总价值最大的一组物品。如果按“单位价值最高”来贪心，很容易出错：一个钻石单位价值超高但太重，塞进去之后剩余容量装不了两个便宜但总价值更高的物品。这种情况下局部最优是钻石，全局最优可能是一堆小物件，贪心直接翻车。

再比如股票买卖问题，如果允许无限次交易但每次有手续费，简单的“见涨就卖”贪心可能被手续费吃掉利润；我需要维护两个状态（持有和不持有）才能算出最优。这种时候就该上动态规划，而不是硬贪。

判断能不能用贪心的一个实用技巧，就是看“当前选择会不会影响未来的可选项”。如果在选择A之后，未来的决策空间被严重压缩，而且没有一个数学性质能保证这种压缩无损，那大概率不能贪心。反过来，如果选择A之后，下一步的决策完全不关心A具体选了哪个，只关心当前状态值，那贪心就很有希望。这就是常说的“无后效性”，也是贪心和动态规划最本质的分水岭。

2. 入门必刷的三种贪心题型：分配、序列与跳跃

2.1 分配类：分发饼干和分发糖果

先看最经典的455. 分发饼干。题目给两个数组，一个是孩子的胃口值g，一个是饼干尺寸s，每个饼干只能喂一个孩子，问最多能满足几个孩子。

这道题看答案觉得很简单，排序加双指针就完了，但自己第一次写很容易绕晕。我当时卡在一点：“到底用饼干去匹配孩子，还是用孩子去匹配饼干？”这里有一个比较稳的解法是先给两个数组都排序，然后用小饼干优先满足小胃口的孩子，一个指针i指向孩子，另一个指针j指向饼干。遍历每一块饼干，如果当前饼干能满足g[i]，i就往后移动一位，最终返回i。

class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i = 0; for (int j = 0; j < s.size() && i < g.size(); ++j) { if (s[j] >= g[i]) ++i; } return i; } };

为什么小饼干优先喂小胃口？因为大饼干是稀缺资源，它既能喂小胃口也能喂大胃口。如果用大饼干喂了小胃口，后面遇到大胃口时可能就没有合适的饼干，导致总的满足数量下降。反过来，小饼干喂不了大胃口，却可以喂小胃口，把小胃口解决掉，大饼干留给大胃口，整体满足数才不会浪费。这就是典型的“让资源匹配恰到好处”。

再看一道容易怀疑人生的分配题：135. 分发糖果。每个孩子至少分到1个糖果，且评分高的孩子要比左右邻居拿得多，求最少需要多少糖果。

我第一次做这道题时，试图一次遍历同时处理左右两边的情况，结果边界判断写得又长又乱，还怎么调都不对。后来才明白，这种“左右都有限制”的问题，正确姿势是拆成两个方向分别处理：先从左往右遍历，只保证右边孩子比左边孩子多（如果评分更高），这个方向可以给所有“右边高”的孩子发够糖果；再从右往左遍历，只保证左边孩子比右边孩子多，同时要取两边计算结果的较大值。

int candy(vector<int>& ratings) { vector<int> candies(ratings.size(), 1); for (int i = 1; i < ratings.size(); ++i) { if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1; } for (int i = ratings.size() - 2; i >= 0; --i) { if (ratings[i] > ratings[i + 1]) candies[i] = max(candies[i], candies[i + 1] + 1); } return accumulate(candies.begin(), candies.end(), 0); }

这道题的核心启发是：当一个约束同时涉及前后两个方向时，贪心策略未必能一次完成，可以把约束拆成两个单方向的贪心，各做一次，最后取交集。这个技巧在不少题目里都能复用，尤其适合处理“既要大于左边，又要大于右边”这类对称条件。

2.2 序列类：摆动序列和最大子数组和

376. 摆动序列要求找出数组中最长的摆动子序列长度。所谓摆动，就是相邻元素的差值一正一负交替出现，比如[1,7,4,9]中差值分别是+6、-3、+5，正负交替。

这道题最关键的观察是：我们不需要真的去删除元素构造子序列，只要统计数组中的“拐点”数量就行。想象你在一张折线图上看走势，连续上涨之后出现下跌的那一瞬间，就是一个转折，只有趋势发生翻转的位置才计入长度。代码里用prediff记录上一次的差值方向，curdiff记录当前差值，当两者一正一负时，说明出现了摆动，计数加一，然后更新prediff。

int wiggleMaxLength(vector<int>& nums) { if (nums.size() < 2) return nums.size(); int prediff = 0, curdiff = 0, count = 1; for (int i = 1; i < nums.size(); ++i) { curdiff = nums[i] - nums[i - 1]; if ((curdiff > 0 && prediff <= 0) || (curdiff < 0 && prediff >= 0)) { count++; prediff = curdiff; } } return count; }

这里有两个细节特别容易错。第一，prediff初始值设为0，是为了让第一个上升或下降趋势也能被判断为一次摆动。第二个细节是平坡的情况，连续相等时curdiff为0，此时不能更新prediff，否则会把平坡后面的真实趋势漏掉。我当初就在这里翻过车：如果不加“prediff <= 0”和“prediff >= 0”这些边界，连续平坡后再转折就会被忽略掉，结果偏小。

53. 最大子数组和是另一个经典中的经典。给定一个整数数组，找出和最大的连续子数组，返回最大和。

贪心思路非常清爽：用一个count变量累加当前位置元素，只要累加结果还大于0，就说明它对后续子数组是有“正向贡献”的，可以继续累加；一旦count变成负数，说明前面的这一段对后面只会拖后腿，直接丢弃，重置为0。遍历过程中不断用count更新答案。

int maxSubArray(vector<int>& nums) { int result = nums[0]; int count = 0; for (int num : nums) { count += num; if (count > result) result = count; if (count < 0) count = 0; } return result; }

这个题有个非常经典的坑：result的初始值不能是0，否则输入全是负数时就会返回0，而不是最大那个负数。我第一次写的时候就把result初值设成0，结果在一个[[-1,-2,-3]]样式的用例上直接错掉。另外，这道题在网上也被归类为动态规划，因为它的滚动变量写法其实就是一维DP的压缩版本，但从贪心角度看也完全说得通，两种视角都能解释，很有意思，值得反复品味。

2.3 跳跃类：从跳跃游戏I到跳跃游戏II

55. 跳跃游戏是贪心题里的风向标。每个位置最多能跳几步，问能不能从下标0跳到最后一个位置。

这道题不建议直接模拟跳跃过程，因为每一步有很多跳法，模拟起来容易漏。更稳的做法是维护一个最远覆盖范围cover，初始是0，然后遍历下标，只要当前下标i在cover范围内，就尝试用i + nums[i]更新cover，让它越远越好。如果cover已经大于等于数组最后一个下标，直接返回true。

bool canJump(vector<int>& nums) { int cover = 0; for (int i = 0; i <= cover && i < nums.size(); ++i) { cover = max(cover, i + nums[i]); if (cover >= nums.size() - 1) return true; } return false; }

关键点是遍历范围不是0到n-1，而是0到cover。如果cover还够不着当前下标i，说明前面的跳跃上限已经到底了，根本走不到i，后面也不用再看了。这个“覆盖范围”的思想，是后续很多贪心题的地基，比如合并区间、视频拼接等，本质都是在维护一个最远能触及的边界。

45. 跳跃游戏II难度升级：假设一定能到达终点，求最少跳几次。

我第一次拿到这题时思考的方向是用回溯，但一看到数组长度是10的4次方量级就放弃了。贪心做法很巧妙：维护两个变量，curEnd表示当前这一步能跳到的最远位置，nextEnd表示再跳一步能到达的最远位置。遍历数组的过程中，不断用i + nums[i]更新nextEnd；当i走到curEnd时，说明这一步覆盖的区域已经全部检查完，还没到终点，那就必须跳一步，步数加一，然后把curEnd更新为nextEnd。

int jump(vector<int>& nums) { int curEnd = 0, nextEnd = 0, step = 0; for (int i = 0; i < nums.size() - 1; ++i) { nextEnd = max(nextEnd, i + nums[i]); if (i == curEnd) { step++; curEnd = nextEnd; } } return step; }

为什么这个贪心是最优的？因为在当前步覆盖的区间内，我选择“跳到能让下一步覆盖范围最大的那个点”，这并不会增加步数，却让未来的可选择范围最大化。相当于每一步都用同样的代价，换取最大的未来收益，自然就是最少步数。我当时反复模拟了好几遍，才真正理解这个“当下边界 + 下一步边界”的双层结构，建议你也多走几遍用例，感受会更深刻。

3. 进阶战术：区间调度与数学类贪心

3.1 区间问题的统一套路：排序是关键

区间类问题是贪心算法里最成体系的一块，几乎可以归类成一个固定套路：排序 + 贪心选择。难点在于搞清楚“按左端点排还是按右端点排”。

我自己的经验是：如果题目要求“为后续区间腾出更多空间”，比如无重叠区间、最少箭射气球，那通常按右端点排序；如果题目要求“把有交集的区间合并起来”，比如合并区间，那就按左端点排序。这个选择的本质原因是，右端点越小，给后面留下的空档越大，贪心策略才有发挥空间；而左端点排序则方便你从头开始顺次合并。

举一个典型例子：452. 用最少数量的箭引爆气球。每个气球在x轴上是左右端点构成的一个区间，一支箭可以射穿所有与之相交的气球，问最少几支箭。

按右端点排序，先拿第一个区间的右端点作为射箭位置。遍历后面每个区间，只要它的左端点小于等于这个射箭位置，说明这支箭能射中它，不需要新箭；一旦出现左端点大于射箭位置，才需要射第二支箭，并更新射箭位置为这个新区间的右端点。

int findMinArrowShots(vector<vector<int>>& points) { sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; }); int arrow = 1; int pos = points[0][1]; for (int i = 1; i < points.size(); ++i) { if (points[i][0] > pos) { arrow++; pos = points[i][1]; } } return arrow; }

这里有个特别容易踩的边界：题目说“两个区间相切时也算能被同一支箭射中”，所以判断条件要用>而不是>=。我因为惯性思维用了>=，结果在相切用例上输出多了1，排查了半天才意识到是边界符号的问题。区间类题目的边界条件经常决定了整个答案的正确性，写之前一定要仔细读题，看区间是开区间、闭区间，还是相切算相交。

类似的还有435. 无重叠区间，按右端点排序后，能保留的区间就是那些“结束早”的区间，删掉多少个等于总数减去能留下的个数。56. 合并区间则按左端点排序，维护当前合并区间的右边界，遇到有交集的就更新右边界，遇到没交集的就收尾并开启新区间。763. 划分字母区间稍微特殊一点，需要先记录每个字母最后一次出现的位置，再遍历字符串不断更新当前片段的最远边界，遍历到边界就切一刀。这几道题可以放在一起集中刷，刷完你会发现区间问题大同小异，核心都是那个排序方向问题。

3.2 数学性质的贪心：取反、加油站与单调数字

有些贪心题不靠区间套路，而是靠数学直觉。比如1005. K次取反后的最大数组和：给定一个数组，可以对任意元素取反，总共操作K次，求最终数组的最大和。

我一开始的想法是每次取反最小的数，但这个策略是错的，因为如果最小数是正数，反复取反它反而是亏的。正确的贪心是：先把数组按绝对值从大到小排序，然后遍历，遇到负数且还有取反次数，就把它变成正数。为什么按绝对值排？因为把绝对值大的负数翻成正数，收益最大，绝对值小的负数翻不翻对总和影响有限。处理完所有负数后，如果K还有剩余，就翻转绝对值最小的那个数，偶数次可以忽略，奇数次会减掉2倍的这个数。

int largestSumAfterKNegations(vector<int>& nums, int k) { sort(nums.begin(), nums.end(), [](int a, int b) { return abs(a) > abs(b); }); for (int i = 0; i < nums.size() && k > 0; ++i) { if (nums[i] < 0) { nums[i] = -nums[i]; --k; } } if (k % 2 == 1) { nums[nums.size() - 1] = -nums[nums.size() - 1]; } int result = 0; for (int num : nums) result += num; return result; }

这个题里面“先翻绝对值大的负数”和“剩余奇数次则翻绝对值最小的数”，每一步都踩在数学规律上，属于典型的“证明之后看起来理所当然，但自己推导容易绕圈”的题目。我的建议是把它和后续的加油站、单调递增数字放到同一天刷，这三道题凑在一起，能极大提升你对“贪心依据”的敏感度。

接着看134. 加油站。环形路线上有若干加油站，每个站可加油gas[i]，去下一站消耗cost[i]，问从哪个站出发能走完一圈。暴力解法是逐一尝试起点，O(n平方)在数据量大时直接超时。

这里有个结论可以先记下：如果所有站的加油总量减去总耗油量的结果小于0，那无论如何都跑不完一圈，直接返回-1。在有解的情况下，贪心策略是：从下标0开始模拟，维护当前剩余油量curSum，一旦curSum小于0，说明从当前起点到当前站之间的任意位置出发都不可能成功，干脆把起点设为i+1，并把curSum重置为0。

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int totalSum = 0, curSum = 0, start = 0; for (int i = 0; i < gas.size(); ++i) { totalSum += gas[i] - cost[i]; curSum += gas[i] - cost[i]; if (curSum < 0) { start = i + 1; curSum = 0; } } return totalSum < 0 ? -1 : start; }

我第一次看到这个解法时觉得很玄学，为什么curSum小于0就把起点直接跳到i+1，而不是往回试探？后来想明白了：如果从start出发到i这里油量已经为负，那从start到i之间任何一个点作为起点，到i时油量只会更少，不会更好，因为这段路上累积的净消耗是负的。所以负区间内不存在可行起点，直接跳到区间后面是安全的。这一条“排除负区间”的推理，就是整个题的灵魂。

最后一题是738. 单调递增的数字，求小于等于n的最大整数，且这个数字每一位从左到右是非递减的。比如332的答案是299，而1234本身就是答案。

做法是先把数字转成字符串，然后从右往左扫描，找到第一个满足s[i-1] > s[i]的位置。找到后把这个位置的前一位减1，并记录一个flag，表示从这个位置后面全部改成9。关键在于要一直从右往左处理，因为减1之后，前面可能又出现不满足单调的情况，比如332：先碰到3>2，记录下标1并让前一位减变成2，字符串变成322；继续往左，又发现3>2，再让下标0减1变成222；最后从flag+1开始全部置9，得到299。

int monotoneIncreasingDigits(int n) { string s = to_string(n); int flag = s.size(); for (int i = s.size() - 1; i > 0; --i) { if (s[i - 1] > s[i]) { flag = i; s[i - 1]--; } } for (int i = flag; i < s.size(); ++i) { s[i] = '9'; } return stoi(s); }

这个题的核心思想就一句话：从高位到低位保证每一位尽量大，但一旦某一位需要减1，为了修复单调性，后面全部拉满成9。这比从头构造要简单得多，也是贪心“每一步选当前最优，然后做修复”的另一个体现。

4. 笔试面试实战：识别贪心与证明策略

4.1 一眼识别贪心题：出题信号与反例验证

刷题多了之后，你会慢慢形成一种直觉。贪心题常见的出题信号有这么几个：题目里出现“最多”“最少”“最大”“最小”“尽可能”“能否达到”这类字眼；输入是一个数组或者一组区间；问题要求你在一系列选择中找最优解，但限制条件里没有像背包那样复杂的多维约束。

拿到这样的题，我先不急着写代码，而是先想：如果每一步都选当前最优，结果会不会被影响？我会动手构造几个最小的反例，比如只有两三个元素的小数组，分别用直觉中的贪心策略和穷举法对比。只要短时间内举不出反例，而且决策确实只依赖当前状态，那贪心就是第一选择。

但这不代表每次都正确。我在实际刷题中总结出一个很管用的流程：先用贪心秒写一版，然后立刻用暴力解法或者小规模随机数据做对拍。对拍跑上几十上百组测试用例，只要结果一致，基本可以放心提交。这个习惯让我避开了很多“看似正确，实则边界翻车”的陷阱。

4.2 证明贪心正确性的三种武器

笔试可以不写证明，但面试时面试官经常追问“为什么贪心是对的”。这时候需要掌握三种常用的证明方法。

第一种是交换论证法，适用于排序类的贪心，比如区间调度、活动安排。先假设最优解中存在两个相邻元素顺序和贪心规则不一致，然后证明交换它们的位置后结果不会变差，从而推出贪心的顺序同样能达到最优。这种方法直观又常用，我写区间题时会刻意用这个思路去组织语言。

第二种是反证法，适用于选择类的贪心。先假设贪心选择的那个元素不在最优解里，然后构造一个包含贪心选择的新解，证明它比原最优解更好，从而产生矛盾。比如K次取反里“优先翻转绝对值最大的负数”这个策略，就可以用反证法：如果不翻转它，转而翻转绝对值更小的负数，总和的增量一定更小，不可能更优。

第三种是数学归纳法，适用于递归结构明显的贪心。先证明第一步贪心选择之后，剩余的子问题仍然是相同结构的贪心问题，而且规模小了一阶，然后由归纳假设得出整体最优。

实际刷题时，我们不需要每次都写完整证明，但至少要能在心里说明白“这个选择为什么不会让后面的结果变差”。这个思考过程本身就会反过来帮你发现隐藏的反例。

4.3 高频踩坑与调试实录

把这段时间踩过的坑集中整理一下，希望你能绕开。

第一个坑是排序方向搞反。区间调度题里，合并区间按左端点排，无重叠区间和射气球按右端点排，搞反了大概率跑出来就是错的。这个没有捷径，只能靠多练，练到“看到题就知道该按哪边排”才算到位。

第二个坑是边界符号用错。跳跃游戏里从左端点相切算可达，要用<=，我一开始用<，结果某几个用例少算了一段。类似的问题在射气球里也出现过，只是方向相反，要用>判断是否需要新箭。

第三个坑是初始值没设好。最大子数组和的result初始值必须是数组第一个元素，而不是0，否则全负数数组会错。这个坑几乎每个刷过这题的人都踩过，属于“不能不知道”的级别。

第四个坑是贪心策略正确，但对特殊输入考虑不周。比如K次取反里，K比负数个数多很多时，剩余次数的奇偶性要单独处理；单调递增的数字里，找到下降点后不能只处理一次，要一路往左处理到尽头。这些边界不是算法思路难，而是细心问题。

再分享一个我一直在用的调试习惯：写贪心题的时候，如果某一步不确定到底怎么选，我会在代码里临时打印每一步的“贪心依据”，比如当前最小值、当前覆盖范围、当前剩余油量，然后对照结果看每一步的选择是否符合预期。另外，强烈建议在本地搭一套对拍脚本，用一个简单的暴力解法做参照，随机生成小数据反复跑。这个小工具帮我省下的时间，远比写它花的时间多。

我个人刷下来最大的体会是，贪心算法的题，难的不是代码，而是“敢不敢用”和“怎么证明”。很多题目用贪心只需要十几行代码，但判断错方向，可能在这十几行里绕半天。另外我强烈建议把贪心题和对应的动态规划题放在一起对比着刷，比如最大子数组和、跳跃游戏都有DP解法，两个版本对照着理解，你对“什么时候贪心够用、什么时候必须DP”的感觉会建立得特别快。最后分享一个小习惯：我每次刷贪心题，都会先在纸上写一句“我这样选，凭什么不会让结果变差”，能答上来再写代码，答不上来就翻题解看证明。这个习惯帮我少走了很多弯路，也推荐你试试。