企业官网建设流程全解析

"糖果"这个标题刚弹出来的时候,我脑子里第一时间跳出来的就是LeetCode 135那道经典题——分发糖果。再配上"贪心"这个标签,基本可以确定:这又是一道让无数人在面试和刷题路上栽过跟头的贪心算法题。说实话,这道题我前前后后刷过好几遍,每次以为自己彻底搞懂了,过段时间再看到还是能琢磨出点新东西。它表面上只是个"发糖果"的小场景,实际上把贪心算法的适用边界、局部最优和全局最优的关系、双方向约束的处理手法全给揉进去了,还顺便能和跳跃游戏II这种覆盖面型贪心构成一组很好的对照组。

这篇文章我不打算只贴一份AC代码就完事。我会把这道题从题意拆解、两次遍历的贪心原理、三种写法(两遍扫描、常数空间优化、分组视角)一直讲到位,然后拉上跳跃游戏II做横向对比,最后把我踩过的坑和面试讲解技巧一并交代清楚。刷过这题的人可以从里面捞点不一样的视角,没刷过的人跟着走一遍也能把贪心这个专题的地基打牢。

1. 题目到底在说什么:读懂"糖果"这道题

先花点时间把题目精读一遍。力扣上的原题编号是135,英文名Candy,国内一般叫"分发糖果"或者"糖果"。题目设定很简单,N个孩子排成一排,每个孩子有一个评分数组ratings,你需要按照两条规则给孩子们发糖果:

• 每个孩子至少分到1颗糖果;
• 相邻两个孩子中,评分更高的那个必须比评分低(或相等)的那个拿到更多糖果。

题目要求返回你最少需要准备多少颗糖果。

注意第二条规则的准确含义:它只说"评分更高"的孩子要比"评分更低"的邻居拿得多,评分相同的时候没有任何约束。我在刚开始刷这题的时候就在这里吃过亏,下意识认为相邻且相等也得给不同数量的糖果,导致用[1, 2, 2]这个用例去验证时,算出5颗,而正确答案是4颗。原因很简单,第二个孩子评分是2,第三个孩子评分也是2,评分相等,第三个孩子拿1颗完全合法。

这个题为什么和"贪心"绑定在一起?因为你要全局糖果数最少,本质上是在每个孩子身上分配一个尽量小的值,而这个值同时受左右两个方向的约束牵制。如果只是单方向(比如只要求左边的孩子评分高就必须多拿),那直接一趟从左到右扫过去就行,每一步只看前一个孩子,这本身就是一个典型的"局部最优叠加成全局最优"的贪心过程。难就难在约束是双向的,一个孩子既可能被左侧约束,也可能被右侧约束,两边都压着的时候,你得取两边约束中更严格的那个。

还有一点值得注意,这道题的正确性从数学上还可以用"每个孩子的糖果数 = max(左侧连续上升长度, 右侧连续下降长度) + 1"来刻画,这为后面几种优化写法埋下了伏笔。这个视角非常重要,它把代码里两个for循环的为什么要做、为什么这么写,彻底讲透了。

2. 贪心思路拆解:为什么要"从左到右"再"从右到左"

2.1 先做一次方向明确的贪心试点

我拿一个具体例子说明。假设评分是[1, 3, 2, 1],正确分配应该是[1, 2, 2, 1]吗?不是。你手动推一下:第1个孩子拿1颗;第2个孩子评分3比第1个孩子高,至少要2颗;第3个孩子评分2比第2个孩子低,但比第4个孩子评分1高,所以第3个孩子必须比第4个多,而第4个至少1颗,于是第3个孩子至少2颗;再看第2个孩子评分3比第3个孩子评分2高,第2个孩子必须比第3个多,那第2个孩子就得是3颗。正确答案是[1, 3, 2, 1],总数7。

从这个过程能发现一个规律:一个孩子最终能拿到的糖果数,取决于他在"左侧递增视角"下的位置,以及他在"右侧递减视角"下的位置,两者取较大值。第1个孩子在两侧都不形成压力,所以是1;第2个孩子在递增链里是第2个,在递减链里也是最高点,两个方向都要求他多拿;第3个孩子在递增视角下是谷底,但在递减视角下比第4个高,所以被右侧约束顶到2。

这就是"从左到右贪心一次,从右到左贪心一次"的直觉来源。从左往右扫,能保证"当前孩子比左边孩子评分高时,糖果数一定比左边多";但这个保证是单向的,它没有任何能力去处理"当前孩子比右边孩子评分高"的场景。比如[1, 3, 2, 1],只做从左到右,得到的糖果数组是[1, 2, 1, 1],第3个孩子在这里拿了1颗,但第4个孩子也是1颗,第3个孩子明明评分更高却和第4个拿得一样多,违反规则。所以必须再从右往左扫一边,把右侧约束补上。

2.2 两次贪心叠加之后,为什么一定是全局最优

有人会问:两次都只做局部调整,一个从左一个从右,加起来就能保证全局最优吗?这里需要从数学上稍微说透一点。

设第i个孩子的最终糖果数为c[i]。第一次从左到右后,c[i]至少满足ratings[i] > ratings[i-1]时,c[i] > c[i-1]。第二次从右到左,用c[i] = max(c[i], c[i+1] + 1)的方式更新,所以等式两边的最优性都是保住的:左边的约束不会被破坏,因为max操作只会把值变大,而变大不会让"比左边多"这个条件失效;右边的约束则通过这一轮补齐。

换句话说,第一个for循环保证了所有"右坡"约束(右边的孩子比左边高)成立,第二个for循环保证了所有"左坡"约束(左边的孩子比右边高)成立。由于任意一对相邻关系,要么属于左坡,要么属于右坡,要么两者都不属于(评分相等),所以最终所有相邻约束全部满足,且每一步都只取满足约束的最小增量,总和就是最小的。这个"分方向处理双向约束"的手法,在后续很多区间类、峰值类问题里都能复用。

我个人的感受是,不要试图一次性同时满足两个方向,那样脑子会绕晕。把双向约束拆成两个单向约束,先修一个方向,再修另一个方向,是贪心题里一个非常好用的套路。

3. 完整实现:代码、复杂度与三种典型解法

3.1 基础版:两次遍历 + 糖果数组,空间O(n)

先把最通用、也最不容易出错的版本贴出来。这个版本我用C++写,逻辑清晰,方便解释:

int candy(vector<int>& ratings) { int n = ratings.size(); vector<int> c(n, 1); // 每个孩子至少1颗 // 第一遍:从左到右,保证评分比左边高时,糖果比左边多 for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { c[i] = c[i - 1] + 1; } } // 第二遍:从右到左,保证评分比右边高时,糖果比右边多 for (int i = n - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { c[i] = max(c[i], c[i + 1] + 1); } } int sum = 0; for (int x : c) sum += x; return sum; }

第一步初始化成1是必须的,"每个孩子至少一颗"这个底线先铺平。第一遍循环从1开始,把每个"右坡"填平。第二遍循环从n-2开始,处理"左坡",这里用的是max(c[i], c[i+1]+1)而不是直接c[i] = c[i+1]+1,这是全题最容易写错的一个点。如果你直接赋值,左边约束已经给到的较大值可能被右边的较小要求覆盖掉。比如评分[1, 3, 2, 1],第一遍后c =[1, 2, 1, 1],第二遍时i = 2,c[2] = max(1, 2)= 2没问题;但假设某种情况下第一遍算出中间值是4,右侧只需要2,直接赋值会把4改成2,左边约束就崩了。所以这个max不是可有可无的铠甲,它是两次贪心叠加的关键粘合剂。

时间上,三次线性遍历,复杂度O(n);空间上多开了一个长度为n的数组,O(n)。

3.2 进阶版:分段统计,把空间压到O(1)

两遍扫描版本已经足以通过所有数据,不过还有更省空间的常数空间写法。思路是把评分序列看成由若干"严格递增段"和"严格递减段"拼接而成,然后对每一段分别处理。这个写法的思路如下:

• 从左到右遍历,维护当前孩子拿到的糖果数pre,以及当前递增段的长度inc、递减段的长度dec;
• 如果当前评分比前一个大,说明处于递增段,pre++(当前孩子至少比前一个多1),inc = pre,dec = 0;
• 如果当前评分和前一个相等,pre = 1,inc = dec = 0(相等时没有约束,只给1颗);
• 如果当前评分比前一个小,说明处于递减段,dec++;如果dec == inc,说明下降段的长度追上了上升段的峰值高度,需要把峰值孩子(也就是上升段最后那个)的糖果数也加1,所以总糖果数res++,pre = 1;
• 每次遍历完一个孩子,把pre累加到总和中。

完整代码:

int candy(vector<int>& ratings) { int n = ratings.size(); if (n == 1) return 1; int res = 1; // 第一个孩子先发1颗 int pre = 1; // 前一个孩子的糖果数 int inc = 1; // 当前递增段长度 int dec = 0; // 当前递减段长度 for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { pre++; res += pre; inc = pre; dec = 0; } else if (ratings[i] == ratings[i - 1]) { pre = 1; res += pre; inc = dec = 0; } else { dec++; if (dec == inc) dec++; res += dec; pre = 1; } } return res; }

这个版本的关键在于if (dec == inc)这个判断。假设上升段已经累积到inc = 3,紧接着来了三个下降点,递减段长度到3时,峰值孩子(就是上升段最后一个,同时也是递减段第一个)必须比递减段里所有孩子都多,此时需要给这个峰值孩子额外加1颗,用dec++来补上这个增量。这里我把代码稍微简化处理了,具体实现时不同人的写法略有差异,但核心思路完全一致。

空间上只需要几个整数变量,O(1);时间还是O(n)。这个写法的缺点是边界情况比较多,不太好记,容易在细节上出错。我建议你面试时优先写两遍扫描版本,常数空间版本当作有余力时的加分项去准备,真要写也需要先在纸上推两个例子再动键盘。

3.3 Python版实现:日常刷题和面试同样够用

Python版本的思路和C++完全一致,代码看起来更紧凑:

def candy(ratings): n = len(ratings) c = [1] * n for i in range(1, n): if ratings[i] > ratings[i - 1]: c[i] = c[i - 1] + 1 for i in range(n - 2, -1, -1): if ratings[i] > ratings[i + 1]: c[i] = max(c[i], c[i + 1] + 1) return sum(c)

3.4 边界用例自测清单

写完代码一定要拿这几组边界用例测试,它们几乎覆盖了所有易错场景:

最后一行留了个思考题,我的答案是[1, 2, 3, 1, 2],总和9。你推的时候注意第二个1右侧还有上升,所以第4个孩子在这里是1颗而不是从头开始累积,推完你就能加深对"每个孩子在两个方向各自的位置"的理解。

4. 和"跳跃游戏II"联动:贪心算法在序列题中的两种典型模式

4.1 跳跃游戏II:贪心的另一张脸

看到热搜词里的"跳跃游戏2 贪心算法",干脆把这道姊妹题也一起拿出来盘一盘。跳跃游戏II的问题是:给你一个非负整数数组nums,你初始在下标0位置,数组里每个元素代表你最多能往后跳多远,问最少跳几次能到达数组最后一位。

这道题的贪心策略非常典型:你在当前位置能跳到的范围内,选择"下一跳能覆盖得更远"的那个位置。每一步都让下一步的可达范围尽可能大,局部最优叠加出来就是全局的跳跃次数最少。实现上我习惯维护两个变量:

• cur:当前这一跳能到达的最远下标;
• next:在cur范围内遍历所有点时,计算得到的下一步最远可达下标。

每遍历到一个新位置,先用i + nums[i]更新next;当i走到cur时,说明当前这一跳已经到极限了,把cur更新成next,跳跃次数加1。代码长这样:

int jump(vector<int>& nums) { int n = nums.size(); if (n <= 1) return 0; int ans = 0, cur = 0, next = 0; for (int i = 0; i < n - 1; i++) { next = max(next, i + nums[i]); if (i == cur) { cur = next; ans++; } } return ans; }

注意循环只到n - 2,因为最后一个位置不需要再跳。i == cur的判断是整个代码的节拍器,它标记了"这一跳覆盖区间的右端点"。区间内的每个位置都被视作潜在起跳点,能到的最远距离不断冲刷next,到达右端点时下一条命就续上了。这也是贪心里很经典的"覆盖区间推进"模式。

4.2 两种贪心模式:约束型贪心 vs 覆盖型贪心

把糖果和跳跃游戏II摆在一起看,能明显看出贪心算法在序列题里的两条分支:

• 糖果题属于"约束型贪心":每个位置的结果受邻居约束,你需要把每个方向的约束拆开、逐个方向满足,然后用max合成最终答案。核心操作是"分方向处理 + 取严格值"。
• 跳跃游戏II属于"覆盖型贪心":每个位置都能扩展出一个可达范围,你需要不断用max扩大覆盖边界,边界走到头时触发一次决策。核心操作是"范围扩展 + 边界触发"。

两者都满足贪心算法的两大前提:贪心选择性质和最优子结构。具体到这两个题,每一次局部决策都不影响后续决策的独立性和整体最优性——糖果题里,无论先从左扫还是先从右扫,另一方向的约束都能独立补上;跳跃游戏II里,每次选择"能跳最远"的点,不会改变后续其他点是否可达的性质。这也是为什么它们能被冠以"贪心"而不是"动态规划"的原因:动态规划通常需要枚举所有子问题的组合才能取最优,而这两道题只在局部做一次决策就行。

如果你刷题时正在准备面试,我强烈建议把这两题当成一组对照题一起整理进自己的笔记:糖果讲的是"双向约束如何拆解",跳跃游戏讲的是"区间覆盖如何推进"。这两个套路分别掌握之后,很多中间难度的贪心题都能往这两个盒子里装。

5. 踩坑记录:这题最常见的几个错误

这部分是我在刷题群、面试复盘、还有自己重刷时总结出来的高频犯错点,逐个列出来给大家避雷。

错误一:只做一次从左到右的遍历。不少第一次接触这题的人会写完第一遍循环就直接返回sum,遇到[1, 3, 2, 1]这种右侧存在下降趋势的数据就挂了。原因前面已经分析过:单方向遍历只能覆盖一半的相邻约束。判断自己是不是只写了一边,就用一个右侧明显有递减的用例去试。

错误二:第二遍循环用直接赋值而不是取max。这是我最爱考别人的一个细节。在从右往左扫时,如果写成c[i] = c[i + 1] + 1,会覆盖第一遍循环已经得到的较大值。记住:max的作用是在满足右侧约束的同时,不破坏左侧约束已经生效的结果。想记住这个点,就反复念叨一句话:第二次贪心的目标是"补约束",不是"重新分配"。

错误三:忽略了评分相等的场景。题目对评分相等的相邻孩子没有任何数量要求,所以相等时只能让后面的孩子回到1颗,不能继续累加。这个坑在[1, 2, 2, 3]这类用例上炸过一次后就会长记性,正确分配是[1, 2, 1, 2],总共6颗,很多新手会算成7。

错误四:初始化全为0而不是1。有些版本一开始把所有c[i]初始化为0,后面再用c[i] = 1之类的逻辑去补齐,边界条件一多就容易漏。不如直接从"每人1颗"出发,把底薪先发到位,后面只处理增量。这样代码更稳,解释起来也更顺畅。

把上面四个错误整理成一张问题速查表:

6. 面试现场:这题怎么讲才能拿高分

最后分享点面试实战经验。糖果这道题在面试中的出现频率非常高,基本是"贪心入门三件套"之一(另外两个是跳跃游戏、加油站)。面试官让你做这题,考察的其实不只是会不会写代码,而是你能不能把"双向约束"这个难点讲清楚。

我的建议是,拿到题后先别急着写代码,先用一个手动例子演示你的思考过程。你可以说:"我先尝试只从左往右扫一遍,发现右边下降的情况处理不了,于是我从右往左再扫一遍,每次用max把两边约束结合。"这句话一说出口,面试官就知道你是在真正分析问题,而不是背模板。紧接着你在纸上写出[1, 3, 2, 1]的推导过程,展示第二遍循环前后的数组变化,这比任何口头解释都更有说服力。

如果面试官追问"能不能优化空间",你可以把O(1)的分段写法思路讲出来,不一定要现场写完整,但至少要把"上升段正常累加,下降段用等差数列求和或者递减计数器处理,当递减长度追上上升峰值时给峰值补发一颗"这个逻辑说清楚。能讲到这一层,基本证明你对题目的理解已经超过大多数候选人了。

还有个小技巧:写完代码后主动说一句"我会用[1,2,2]和[1,3,2,1]这两个用例自查一下",然后快速在脑子里过一遍结果。这种行为会给人留下"训练有素、有工程习惯"的印象,比解完题就干坐着等下一题要加分得多。

至于刷题训练的建议,我的心得是:贪心算法不能靠死记硬背,必须建立"局部最优为什么会等于全局最优"的直觉。每次遇到一个贪心题,先问自己三个问题——这个问题的约束是什么方向?局部决策是什么?这个决策会不会影响后续决策?糖果题的答案是"约束是双向的,局部决策是取满足约束的最小增量,不会影响其他节点的独立约束",跳跃游戏II的答案是"约束是单向覆盖,局部决策是选覆盖最远的点,不会影响可达性"。这三个问题回答清楚了,贪心题基本就稳了。