企业官网建设流程全解析

刷题打卡到第 28 天，这天做的四道题非常有意思：122、买股票的最佳时机 II，55、跳跃游戏，45、跳跃游戏 II，还有 1005、K 次取反后最大化的数组和。放在一起看，这四道题全部是贪心算法的经典应用，而且难度跨度从 Easy 到 Medium，层层递进，非常适合集中训练“贪心思维”。

如果你正在准备算法面试或者刷 LeetCode 卡在贪心这一类，我的建议是把这四题当成一个小专题来处理。因为它们的套路极度相似：先想清楚局部最优是什么，再证明局部最优能推出全局最优，最后落地成代码往往只有十来行。这篇就把我做这四题时的完整思考过程、代码实现、还有踩过的坑一次性掰开揉碎讲清楚，希望能帮你少走点弯路。

1. 为什么把这四道题放在一起刷

1.1 四道题的核心考点

先说说这四道题各自的“题眼”。122 题是股票买卖的变体，允许多次交易，问最大利润；核心考点在于你能否想到“只要今天比昨天贵，我就把这段差价赚到手”这个朴素结论。55 题是跳跃游戏，判断能不能从数组起点跳到终点；核心考点是贪心地维护一个“最远能覆盖到哪里”的边界。45 题是跳跃游戏的升级版，不仅问能不能到，还问最少跳几次；核心考点变成了在覆盖区间内继续扩展下一个覆盖区间。1005 题则是 K 次取反后最大化数组和；核心考点很直接：每次取反都应该优先让当前数组和变得更大，也就是优先处理负数。

表面上这几道题完全没有关系，一个是金融问题，两个是数组跳跃问题，一个是数组修正问题。但它们的底层思路是同一个：每一步都做当时看起来最优的选择，不回头，不全局搜索，最终却能得到全局最优解。

1.2 贪心算法的共性套路

很多新手一听到贪心就觉得“玄学”，其实它的套路非常固定。我做题总结下来，贪心算法一般就三步。

第一步，定义清楚“局部最优”。比如 122 题里，局部最优是“每一段上涨我都不放过”；55 题里，局部最优是“每一步都把下一次能跳的最远距离更新到最大”；1005 题里，局部最优是“每一次取反都选择当前对数组和增益最大的那个元素”。

第二步，证明局部最优组合起来等于全局最优。这一步在面试中很关键，但在刷题时可以适当弱化理解。比如 55 题，你每一步都尽量把覆盖范围扩大，只要覆盖范围能覆盖到终点，那全局上一定存在一条可行路径，因为每一步的覆盖范围是连续扩展的，不存在“跳过了某个关键点”的漏洞。

第三步，把策略翻译成代码。贪心的代码往往很短，短到有时候你会怀疑“就这么简单？不会漏情况吧”。这是正常的，贪心的难点从来不在实现，而在你敢不敢确认自己的贪心策略是对的。

记住这个三步框架，后面四道题我们全部套着它走。

2. 122、买股票的最佳时机 II：最容易想复杂的一道题

2.1 题目意思与常见误区

题目给你一个数组 prices，prices[i] 表示第 i 天的股票价格。你可以在任意一天买入，在之后的任意一天卖出，而且可以多次交易，但手里同时只能持有一只股票。问能获得的最大利润。

我第一次做这题时，第一反应是模拟：找到波谷买入，找到波峰卖出，然后再找下一个波谷，再找下一个波峰。这个思路没错，但实现起来很容易把自己绕晕，因为波峰波谷的判断要处理一堆边界情况。后来我才意识到，这题根本不需要真的去“找波谷波峰”。

还有一个常见的误区是：有人会把“多次交易”理解成“每两天做一次买卖”。比如 [1,2,3,4] 这种单调上涨的数组，有人会觉得既可以从 1 买到 2，再从 2 买到 3，再从 3 买到 4，而实际最大利润是 3，也就是从 1 持有到 4。虽然这类人结果算对了，但理解的粒度不对，写出来的代码会很别扭，而且容易在更复杂的用例上翻车。

2.2 贪心策略的推导过程

这题的贪心策略一句话就能说清楚：只要 prices[i] > prices[i-1]，就把差价 prices[i] - prices[i-1] 累加进答案。

为什么这个策略是对的？我们分两种情况来看。

第一种，连续上涨的曲线，比如 [1,2,3]。按照策略，累加 (2-1)+(3-2)=2。而实际最优操作是第 0 天买入，第 2 天卖出，利润也是 2。你会发现累加每一段的差价，等价于从起点持有到终点，数学上就是一个 telescoping sum，中间项全部约掉了。

第二种，有涨有跌的曲线，比如 [1,5,3,6]。策略累加的是 (5-1)+(6-3)=7。而实际最优操作正是 1 买 5 卖，3 买 6 卖，利润 7。这里的核心逻辑是：遇到下跌（5 到 3）时，我不但不亏钱，反而通过“假装卖出再买入”把利润落袋，同时重置了持仓成本。这本质上就是把每次上涨都单独拿出来交易。

局部最优就是“每次上涨都赚到”，全局最优就是“所有上涨段的总和”。因为下跌段不产生利润，我们没有承担任何下跌损失，所以这个策略一定是最优的。

2.3 代码实现与复杂度分析

def maxProfit(prices): profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] return profit

代码就这么多，时间复杂度 O(n)，空间复杂度 O(1)。我见过很多人在这题上写出二三十行的动态规划解法，也不是不行，但既然贪心几行就能解决，面试时优先写贪心，然后跟面试官提一句“如果限制交易次数就得换成动态规划”，反而能展示你对题目边界的把握。

注意：这道题有个变体是 121 题，只允许一次交易，那贪心就不成立了，必须用“记录历史最低点”的办法。千万不要把这两题的解法搞混。

3. 55、跳跃游戏：只关心最远覆盖范围

3.1 从“能不能跳”到“覆盖区间”

55 题是这么描述的：给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

我最初自己尝试做这题时，写了个 DFS + 记忆化，能过是能过，但总觉得很重。后来看了别人的题解才意识到，这题根本不需要模拟具体的跳法。你只需要维护一个变量 maxReach，表示当前能到达的最远下标。遍历数组时，只要当前位置下标在 maxReach 范围内，就说明当前位置是可达的，然后尝试用 nums[i] + i 去更新 maxReach。如果某一步 maxReach 已经大于等于最后一个下标，直接返回 true；如果遍历完了还没达到，返回 false。

这里的关键思维转变是：不要关心“我怎么跳过去的”，只关心“我目前能覆盖到的最远范围是不是包含当前位置”。这就像玩贪吃蛇，你不需要知道蛇身每一节是怎么长的，你只需要知道蛇头现在最多能伸到哪里。

3.2 代码实现与两个边界条件

def canJump(nums): maxReach = 0 n = len(nums) for i in range(n): if i > maxReach: return False maxReach = max(maxReach, i + nums[i]) if maxReach >= n - 1: return True return False

这段代码有两个极其关键的判断，新手特别容易漏。

第一个是if i > maxReach: return False。这个条件表示当前位置根本不可达。因为 maxReach 是前面所有位置能到达的最远下标，如果当前位置的下标已经超过了它，说明中间出现了断档，后面的位置永远不可能跳到，直接返回 false 即可。

第二个是if maxReach >= n - 1: return True。这个是提前终止条件。因为一旦覆盖范围已经到达或超过终点，后面就不用再看了。有些实现会在循环结束后才返回 true，那种写法在语义上没错，但多做了无用功。实测下来，提前返回在极端用例（比如终点在前几个位置时就已覆盖）里能省掉不少不必要的遍历。

3.3 为什么“每一步最大”就是全局可达

很多人会问：每一步都把覆盖范围扩到最大，会不会漏掉某条路径？比如当前在位置 2，能跳到位置 5，但也许跳到位置 3 才能再跳到终点，而直接跳 5 反而跳过头了？

这个问题正是贪心证明的核心。实际上，maxReach 表示的是“可达下标的一个连续区间”。因为从当前位置 i 出发，你可以跳到 [i, i+nums[i]] 区间内的任意一个位置。如果 maxReach 能到 5，那意味着从起点到 5 之间所有位置都是可达的。所以当你站在某个位置时，你能覆盖的是一个连续的前缀区间，不存在“跳过头”导致中间点不可达的情况。既然整个区间都可达，那么任何可能的跳跃路径都不会被贪心策略漏掉。这就是为什么贪心在这里是正确的。

4. 45、跳跃游戏 II：最少跳几次

4.1 与 55 题的本质差异

45 题和 55 题几乎是孪生兄弟，题目同样给了 nums 数组，但这次保证你能到达最后一个下标，要求计算最少跳跃次数。输入保证有解，这省去了不可达判断，但难度反而上来了，因为“最少”两个字要求你必须在多个可行方案里选出最优。

我最初做这题，想的比较笨：能不能用 BFS 或者动态规划？BFS 确实能做，把每个位置看成图的节点，能跳到的位置看成边，求最短路。动态规划也能做，dp[i] 表示到达位置 i 的最少跳跃次数，转移时遍历所有能到 i 的位置。但这两种做法的时间复杂度都偏高。BFS 的最坏情况接近 O(n^2)，动态规划也是 O(n^2)，在 LeetCode 的测试数据下虽然能过，但显然不是最优解。

这题的贪心思路其实是一个“区间扩展”的思维。你把当前这一跳能到达的所有位置看作一个区间，那么下一跳能到达的最远位置，就是这个区间内所有位置再往外跳一格的最大值。你只需要在区间扩展时计数跳跃次数即可。

4.2 双边界维护的贪心写法

维护两个变量：curEnd 表示当前这一跳能到达的最远位置，nextEnd 表示在 curEnd 范围内遍历时，下一步能到达的最远位置。从头遍历数组，不断更新 nextEnd。当 i 到达 curEnd 时，说明当前这一跳已经走到尽头，必须先跳一次，然后把 curEnd 更新为 nextEnd，跳跃次数加一。如果 curEnd 已经覆盖终点，直接返回跳跃次数。

def jump(nums): n = len(nums) steps = 0 curEnd = 0 nextEnd = 0 for i in range(n - 1): nextEnd = max(nextEnd, i + nums[i]) if i == curEnd: steps += 1 curEnd = nextEnd if curEnd >= n - 1: break return steps

注意这里遍历范围是range(n - 1)，不包括最后一个位置。因为达到最后一个位置时，跳跃已经完成，不需要再统计下一次跳跃。我第一次写的时候用range(n)，在边界用例 [0] 上就出错了，steps 被多加了一次。这是一个非常容易翻车的细节。

这段代码的时间复杂度 O(n)，空间复杂度 O(1)。相比动态规划的 O(n^2)，提升非常明显。而且这个思路和 55 题几乎是一脉相承的：55 题是维护一个覆盖区间，45 题是在覆盖区间的基础上继续维护“下一跳覆盖区间”，本质上是同一个模型多走了一步。

4.3 一个帮助理解的例子

看一个容易困惑的用例：nums = [2,3,1,1,4]。

初始 curEnd = 0，nextEnd = 0。

i=0 时，nextEnd = max(0, 0+2) = 2。i 等于 curEnd，所以 steps 变 1，curEnd 变为 2。

i=1 时，nextEnd = max(2, 1+3) = 4。i 还没到 curEnd，继续。

i=2 时，nextEnd = max(4, 2+1) = 4。i 等于 curEnd，所以 steps 变 2，curEnd 变为 4。此时 curEnd >= n-1，退出。

最终返回 2。而这个数组的最少跳跃次数确实是 2：从 0 跳到 1，再从 1 跳到 4。

这个例子里最容易犯的错是：在 i=1 时发现 nextEnd 已经到 4 了，就急着把 steps 加一，结果导致 steps 变成 2。但仔细想想，i=1 还在第一跳的覆盖范围内，第一跳还没结束，你根本还没跳出去，怎么能提前计第二跳的次数？所以只有当 i 走到 curEnd 时，才意味着“当前这一跳覆盖的区间已经全部遍历完，必须做下一跳的决策了”。这是这个算法最微妙的点，理解透了，整个题就通了。

5. 1005、K 次取反后最大化的数组和

5.1 题目与贪心策略分析

1005 题的描述很简单：给你一个整数数组 nums 和一个整数 k，你可以对数组中的任意一个元素执行取反操作，总共只能执行 k 次，求执行完所有操作后数组和的最大值。同一个元素可以重复取反。

我第一次看完题目，第一反应是：每次都让当前数组和最大，那不就是每次取反当前数组里最小的数吗？这个直觉方向是对的，但实现上有一个非常隐蔽的问题。

先梳理贪心策略。取反一个数是正数，会减少数组和；取反一个数是负数，会增加数组和。所以要最大化和，显然应该优先取反负数，而且是绝对值最大的负数，也就是最小的那个数。

如果负数的数量不足 k，也就是说负数全部取反完之后还有剩余次数，这时就需要考虑取反正数了。正数中最小的那个被取反，损失最小。但这里有个变数：如果正数里最小的是 0，或者取反后可以再次取反回正数，那结果就会有变化。实际上，当所有负数都被取反以后，剩余的 k 次操作都作用在同一个数上。如果剩余次数是偶数，可以反复取反最终回到原值；如果是奇数，那么最终会对最小的正数（或 0）做一次取反。

5.2 一个直观优先级：负数变正优先

所以实现思路是：先按照绝对值从大到小排序，这样可以保证在处理负数时，优先取反绝对值最大的负数。处理完整数组后，如果 k 还有剩余且 k 是奇数，就把当前数组中最小的那个数取反，否则不用动。

def largestSumAfterKNegations(nums, k): nums.sort() for i in range(len(nums)): if nums[i] < 0 and k > 0: nums[i] = -nums[i] k -= 1 if k % 2 == 1: nums.sort() nums[0] = -nums[0] return sum(nums)

这个版本比较好理解，先排序让负数集中在左边，遍历时把负数逐个取反。k 用完就停。如果最后 k 还剩奇数，说明多出的这一次取反无法抵消，只能牺牲绝对值最小的数，也就是排序后第一个数，取反它。

这里的排序有个细节：第一次排序是为了让负数都靠前，第二次排序是在所有数都变成非负后，找到最小值。严格来说，第二次可以不用完整排序，用 min(nums) 找最小值即可，但排序写起来更省心，反正数组长度通常不大。我实测时，min 版本的性能会好一点点，但对刷题来说差别可以忽略。

5.3 另一种思路：优先队列模拟

除了排序，还有种更贴近“模拟”的写法：用小顶堆每次弹出最小值，取反后重新入堆，重复 k 次。这样每次操作都在全局最小的数上进行，能保证每步局部最优。代码也比较直观：

import heapq def largestSumAfterKNegations(nums, k): heapq.heapify(nums) for _ in range(k): smallest = heapq.heappop(nums) heapq.heappush(nums, -smallest) return sum(nums)

时间复杂度是 O(k * log n)，当 k 很大时效率不高。相比之下，排序法 O(n log n) 更稳定。但我推荐新手先写优先队列版本，因为它的逻辑和“每次取反当前最小数”的直觉完全一致，不容易出错。等理解了，再切换到排序法，体会一下如何用排序来模拟“多次全局最小操作”。

注意：这里有一个 K 次取反的关键陷阱。有人会写“把所有负数取反后，拿剩余 k 直接对第一个元素连续取反 k 次”，这是可以的，但要注意如果 k 是偶数，取反两次会回到原值，等于没变。所以判断时不能只看剩余 k 是否大于 0，必须看 k 的奇偶性。

6. 整个 Day28 刷下来，我总结的贪心实战避坑清单

6.1 四道题统一思维模板

做完这四道题，我发现贪心算法刷题时有一个特别实用的统一模板，几乎可以直接套用：

第一步，先找“每一步的局部最优策略”。这句话说出来很简单，但做起来难。难点在于你必须先想清楚“步”的单位是什么。122 题里，“步”是每一天的相邻差价；55 题里，“步”是每一个位置能扩展的最远距离；1005 题里，“步”是每一次取反操作。

第二步，画几个边界用例来验证策略。比如 45 题，一定要手动跑一遍 curEnd 和 nextEnd 的变化过程；1005 题一定要试 k 是奇数或偶数两种情况。边界用例能帮你挡住大部分“感觉对了但其实漏了情况”的 bug。

第三步，写代码时保持变量语义单一。我见过很多贪心代码写得混乱，根源就是同一个变量混用了多种含义。比如 45 题里 curEnd 和 nextEnd 如果混为一谈，后面铁定出错。宁可多声明一个变量，也要让代码读起来像伪代码一样清楚。

6.2 实际刷题过程中我踩过的坑

第一坑：122 题里，有人为了省一行代码，直接用profit += max(0, prices[i] - prices[i-1])，这样写确实更简洁，但如果面试官让你解释贪心策略，你必须能说出 max 隐藏了什么逻辑，而不能只是背代码。

第二坑：55 题里，很多题解会在 for 循环里先判断if maxReach >= n - 1: return True，再判断if i > maxReach: return False。这两个判断的顺序特别重要。我之前先判 i > maxReach，结果在某个用例里因为顺序问题提前返回了错误的 true。建议的写法是先判不可达，再判可达，这样逻辑链条是“当前位置不可达就返回 false，否则更新，更新后如果够到终点就返回 true”，层次清楚，不容易错。

第三坑：45 题里，curEnd 的更新时机。我最初用 while 循环写，条件写的是while i <= curEnd，结果在 curEnd 一直不变的情况下死循环。后来改成 for 循环遍历，彻底绕开了这个问题。for 循环天然有一个指针在前进，不会陷入死循环，代码也更短。

第四坑：1005 题里，所有负数取反完之后，我一开始写的是if k > 0: nums[0] = -nums[0]，完全没考虑奇偶性。结果遇到 nums = [1], k = 2 这种用例，正确答案是 1，因为取反两次又回来了，我的代码却输出 -1。后来加上k % 2 == 1的判断，才算是真正搞明白了。

6.3 这四道题做完之后，还能怎么扩展

如果是准备面试，我建议把这四道题放在一起复习，同时联想几个变体问题，你可以自己先想一想：

第一，122 题如果加上“卖出后第二天才能买入”的限制，贪心还成立吗？如果加入手续费呢？这个时候题的分类就变成了状态机 DP，需要用一个二维 dp 数组来记录“持有”和“不持有”两种状态。

第二，55 题和 45 题，如果把“最大跳跃长度”改成“每次随机跳一个值”，还能用贪心吗？显然不能，那就变成动态规划了。所以贪心的边界就在于“当前选择不受未来未知信息影响”。

第三，1005 题如果允许取反任意次数但每次代价不同，那又变成了另一类问题。不过这些都是后话，把 Day28 的四个基础模型吃透，遇到变体时你至少能快速判断出“贪心不成立，要换 DP”，这本身就是一种很重要的能力。

我个人在实际刷题里的体会是：贪心算法最怕的不是不会写代码，而是“觉得自己的策略是对的，但说不清楚为什么”。所以每做完一道贪心题，花两分钟在心里把“局部最优是什么，为什么能推出全局最优”讲一遍，这个习惯比多刷十道题都管用。Day28 这四题正好是练这个习惯的绝佳素材，建议你也试试。