1. 先说结论这道 Hard 题难在“想做复杂”不难在代码LeetCode 1402 Reducing Dishes做菜顺序是我见过最典型的“标签 Hard、思路 Medium、代码 Easy”的题。题目给你一个数组satisfaction每道菜有一个“喜爱值”你可以自由选择做哪几道菜也可以自由决定上菜顺序。最后的总分是每道菜的喜爱值 × 它的顺序编号编号从 1 开始。换句话说第一道菜系数是 1第二道菜系数是 2以此类推。你可以一道菜都不做所以答案至少是 0。这道题在 LeetCode 上被标记为困难但真正的代码量不到 10 行。很多人在评论区第一反应是“这不就背包 DP 吗”也有人直接把负数全部过滤掉结果都跑偏了。实际上最优策略藏在一个很自然的贪心里先按满意度从大到小排序然后依次判断“当前这盘菜加进去能不能带来正向收益”能加就加不能加就停。就这么简单。这篇文章会从题意拆解、贪心推导、DP 兜底、边界条件、面试写法五个角度完整讲一遍。不论你是第一次刷 Hard 题还是在准备面试想快速过题都可以直接参考下面的思路和代码。1.1 题意一句话讲清楚假设你是一个厨师手上有若干道菜每道菜有一个satisfaction[i]。你决定做其中若干道并且自己安排上菜顺序。如果某道菜被安排在第 k 个位置那么它贡献的分数就是k * satisfaction[i]。注意编号从 1 开始不是从 0 开始。核心限制有三个可以选任意子集不是必须全做。可以任意排列顺序不要求保持原数组顺序。可以一道都不选此时分数为 0。举官方示例satisfaction [-1, -8, 0, 5, -9]最优答案是 14。一种达到 14 的上菜顺序是[-1, 0, 5]计算过程为第 1 道-1 × 1 -1第 2 道0 × 2 0第 3 道5 × 3 15总分-1 0 15 14。这里很多人会犯第一个错误看到负数就觉得不能选。但如果不选-1只选[0, 5]总分是0×1 5×2 10。选了-1之后虽然第一道菜贡献了 -1但它把5从系数 2 推到了系数 3多出来的收益正好是5 - 1 4。所以负数不一定坏事关键看它“垫在队首”之后能不能带来更多正向收益。1.2 难度标签为什么是 Hard这题被标成 Hard不是因为解法本身难写而是因为你需要想清楚“为什么排序后贪心是对的”。如果直接上来写 DFS 枚举所有子集和排列n 最多 500完全不可行。如果写 0/1 背包 DP也能做但复杂度是 O(n²)代码更重。LeetCode 的困难题经常是这种类型问题描述短数学直觉藏在后面能一眼看穿的人 5 分钟写完看不穿的人会卡很久。这道题在热门 100 题、每日一题和周赛讨论里都经常被提起很多人把它和“基本计算器”这种需要精心维护状态的困难题放在一起比较。但 1402 几乎没有语法解析成本它考察的是排序后的增量思维。你先把这个核心抓住后面所有代码都是顺水推舟。2. 贪心解法的整个推导过程2.1 第一步最优排列一定满足“喜爱值越大位置越靠后”先看一个关键性质如果最终选定了若干道菜那么它们的相对顺序一定有迹可循。假设有两道菜喜爱值分别是 a 和 b并且 a b。如果当前 a 在第 p 位、b 在第 q 位且 p q也就是大的菜放在了更靠前的位置。这时候如果把这两道菜交换新的分数减去旧的分数的变化是p × b q × a - (p × a q × b) (q - p) × (a - b)因为 q p且 a b所以这个差值一定大于 0。也就是说把较大喜爱值的菜往后挪把较小喜爱值的菜往前挪总能提高总分。所以无论你最终选哪些菜最理想的相对顺序一定是“喜爱值从小到大排列”。这个结论非常重要它把“任意排列”这个问题直接化简成了“选哪些菜组成一个升序序列”。2.2 第二步把选菜过程看成“不断在队首插入新菜”既然最终顺序是升序那么我们可以换一个构造角度从最大值开始一路往左扩展。假设当前已经选好 k 道菜它们的喜爱值之和是S当前最优分数是T。现在来了一道新菜值为 x而且 x 比当前已经选的所有菜都小。如果我想把 x 加进最终菜单按照升序排列它会被放在队首。这会导致原来 k 道菜全部往后挪一位也就是每个原菜的系数都加 1。所以新增的总收益是原来的 k 道菜系数整体加 1额外增加S新菜 x 放在第 1 位贡献x × 1 x总增量 S x因此是否加入这道菜只需要看S x是否大于 0。这个公式就是整道题的题眼。回头看官方示例排序后是[5, 0, -1, -8, -9]。先选 5此时S 5分数为 5。再看 0S 0 5 0加入 0分数变成5 5 10S 5。再看 -1S (-1) 4 0加入 -1分数变成10 4 14S 4。再看 -8S (-8) -4已经小于 0后面也不用看了。最后答案就是 14。2.3 第三步为什么可以直接 break按照降序扫描时如果当前这道菜已经让S x 0那后续的菜会怎样因为是降序排列后续所有菜的喜爱值都小于等于 x而S在当前这一轮没有变化。所以对任意后续菜 y都有S y S x 0也就是说后面的菜只会带来负收益或零收益不可能再让总分增加。因此果断break不需要继续扫描。这个结论保证了贪心是一个严格的 O(n log n) 算法排序是唯一的主要耗时。这里额外说一点我习惯写 0而不是 0因为增量公式的语义是“严格正向收益”。等于 0 说明不赚不亏虽然在这题里写成 0通常也能过但面试时很容易被追问“等于 0 为什么选/不选”解释起来会绕。直接用 0最干净。3. 核心代码实现与复杂度3.1 Python 贪心实现from typing import List class Solution: def maxSatisfaction(self, satisfaction: List[int]) - int: satisfaction.sort(reverseTrue) ans 0 cur_sum 0 for x in satisfaction: if cur_sum x 0: ans cur_sum x cur_sum x else: break return ans这段代码很直观cur_sum表示当前已选菜品的喜爱值总和也就是公式里的S。ans表示当前已经累积的分数。如果cur_sum x 0说明加入 x 能带来正向收益执行加入。否则直接退出因为后面的菜值更小更不可能带来收益。拿[5, 0, -1, -8, -9]来模拟当前菜品 xcur_sum x是否加入更新后 ans更新后 cur_sum55是5505是105-14是144-8-4否退出1443.2 C 实现class Solution { public: int maxSatisfaction(vectorint satisfaction) { sort(satisfaction.rbegin(), satisfaction.rend()); int ans 0; int curSum 0; for (int x : satisfaction) { if (curSum x 0) { ans curSum x; curSum x; } else { break; } } return ans; } };C 版本同样简单。sort(satisfaction.rbegin(), satisfaction.rend())直接降序排列省掉自定义比较器。需要提醒的是int在这个数据范围内完全够用因为 n 最大 500所有菜都是 1000 时最大分数也只有1000 × (1 2 ... 500) 125250000不到 1.3 亿。但如果你在面试中不放心写成long long也不会被扣分。3.3 DP 写法没看出贪心时的兜底方案如果你在考场上没能快速推导出贪心也可以用排序 0/1 DP 兜底。排序后所有被选中的菜在最终答案里的相对顺序天然就是升序所以我们可以按顺序扫描记录当前“已经选了几道菜”。状态定义dp[i][j]表示考虑前 i 道菜并且选了 j 道菜时的最大分数。转移时当前菜要么不选要么作为第 j1 道菜选进去。from typing import List class Solution: def maxSatisfaction(self, satisfaction: List[int]) - int: satisfaction.sort() n len(satisfaction) NEG -10 ** 9 dp [[NEG] * (n 1) for _ in range(n 1)] dp[0][0] 0 for i in range(n): for j in range(i 1): if dp[i][j] NEG: continue # 不选当前菜 dp[i 1][j] max(dp[i 1][j], dp[i][j]) # 选当前菜作为第 j1 道菜 dp[i 1][j 1] max( dp[i 1][j 1], dp[i][j] (j 1) * satisfaction[i] ) return max(dp[n])这个做法的时间复杂度是 O(n²)空间也是 O(n²)。n 最多 500完全能过但显然没有贪心优雅。DP 的价值在于即使你没想到增量公式也能通过“排序消除排列不确定性 选/不选背包”的思路拿到答案。如果你在面试中先说 DP 再说贪心反而能体现你掌握多种解法。3.4 为什么不用考虑“全不选”的额外处理ans初始化为 0天然处理了什么菜都不做的情况。如果数组全是负数降序排序后第一个数就小于等于 0cur_sum x 0直接 break返回 0。不需要单独写if max(ans, 0)之类的代码。这看起来是小事但很多人写 DP 时会忘记答案还要和 0 取最大值而贪心写法把这个边界吃掉了。4. 边界条件与常见错误4.1 全是负数例如satisfaction [-3, -2, -1]。所有菜都做总分为-3×1 - 2×2 - 1×3 -10。做一部分也不如不做所以答案就是 0。贪心代码会在第一个数-1时判断0 (-1) 0直接退出返回 0。这类用例考察的是你对“可以一道都不做”的理解。很多第一次刷题的人会把所有负数加起来得到一个负数答案然后才发现题目下限是 0。4.2 负数和 0 的组合比如satisfaction [-1, 0, 2]。最优选择是[-1, 0, 2]分数为-1×1 0×2 2×3 5。如果不选负数只选[0, 2]分数是0×1 2×2 4。负数在这里起到了“垫高系数”的作用。更极端一点[0]和[0, 5]这类带 0 的用例也值得注意0 本身贡献为 0但放在正数前面会把正数的系数整体往后推所以该选就选。贪心代码里cur_sum x 0对 0 是天然成立的因为如果当前已经选了正数cur_sum大于 0那么cur_sum 0 00 也会被加入。4.3 用 0会怎样关于判断条件我前面提到写 0更标准。如果你写成 0在大多数测试用例下也不会挂因为cur_sum x 0说明当前增量是 0加入后总分不变但后面不会再出现正收益。不过面试时考官如果追问“等于 0 算有收益吗”你很难自洽。实战建议是严格使用 0少给自己挖坑。4.4 排序方向不能搞反我见过有人排序升序之后从前往后扫然后直接判断当前元素是否大于 0这是错误解法。升序的正确做法是从后往前扫或者转成降序再扫。逻辑核心是从最大喜爱值开始尝试而不是从最小开始。如果从最小开始你根本不知道后面会不会有更大的菜来救它增量公式的前提就变了。为了减少出错建议直接写成reverseTrue或者rbegin()让代码和推导过程一一对应。4.5 边界用例速查表输入最优选择分数说明[-1, -2, -3]不选0全负数[0, 0, 0]不选或全选00 不改变分数[4, 3, 2][2,3,4]20全正数全部选[-9, -8, -1, 0, 5][-1,0,5]14负数可以垫系数[0, 5][0,5]100 也有位移价值5. 从“做菜顺序”抽象出来的通用套路5.1 什么时候会想到“排序 增量收益”这类题有一个很明显的信号分数和位置有关而且你可以自由重排。典型特征包括选择若干元素任意排列。每个元素对答案的贡献取决于它被放在第几个位置。元素本身有正有负不能简单地全部选。遇到这种题第一步永远是找“最优排列”的性质而不是直接上搜索。对于本题交换论证告诉我们最优顺序一定是升序一旦顺序确定选择就变成了“从大到小依次尝试加入”。类似的套路在区间调度、任务调度等问题里也很常见核心都是先排序再通过增量公式判断加入是否有利。顺便说一句LeetCode 上很多困难题包括“基本计算器”这类需要状态机思维的问题和 1402 是完全不同的类型。1402 不考复杂状态只考数学直觉。如果你刷题时看到 Hard 标签就条件反射往 DP 想很容易错过更简单的贪心。当然DP 是很好的兜底但先用几分钟做数学观察往往能省下大量时间。5.2 一个扩展如果题目要求输出具体做菜顺序只需要在贪心过程中记录被选中的菜。由于扫描顺序是降序记录下来的列表是降序的比如[5, 0, -1]。最终上菜顺序把记录列表反转即可变成[-1, 0, 5]。这是因为我们始终保持“后加的更小放在队首”的构造逻辑反转后就是升序排列。如果面试官追问“最优选择是不是一定是降序排序后的一段前缀”答案也是肯定的。因为贪心在第一次遇到非正收益时就 break后面的元素不再考虑所以被选中的元素恰好是降序排序后的一个前缀。这个额外观察可以用来手算验证把降序数组的前 k 个元素取出来反转后算总分和贪心得到的结果一致。5.3 复杂度分析该怎么讲时间复杂度排序 O(n log n)一次线性扫描 O(n)所以总复杂度 O(n log n)。空间复杂度排序原地进行额外空间 O(1)不考虑递归栈。如果是 DP 写法时间复杂度 O(n²)空间复杂度 O(n²)。在面试中推荐先说贪心代码短、复杂度低、边界也少。然后把 DP 作为“如果没看出性质”的备选方案提到面试官会认为你有完整的思考层次。6. 我的做题复盘与几条实战习惯6.1 我第一次做这题的真实过程我第一次做 1402 时第一反应也是 DP因为在 LeetCode 上看到 Hard 标签会本能地往复杂方向想。我先把数组升序排序然后写了一个二维 DP跑了几个用例都能过但总觉得不够痛快。后来我看到别人的解法只有几行才意识到自己漏掉了增量思维。复盘时我重新推导了一遍发现关键就是S x 0这个式子。从那以后我遇到“任意排列 位置权重”的题会先停下来想“能不能通过交换论证确定排列顺序”而不是急着写状态转移。6.2 现场写代码时的几个习惯我习惯把变量名写清楚比如cur_sum而不是sans而不是res。不要小看命名面试时你需要一边写一边解释好的变量名能让你的思路外化。写完代码后我会立刻用两个用例自测一个全负数一个是官方示例。全负数保证答案兜底为 0官方示例保证主流程没有明显错误。另外一个很实用的习惯如果第 3 分钟还没有思路不要继续硬想贪心。先退回 DP因为 O(n²) 在 n 500 时完全能过。有时候“先写 DP再继续找贪心”比“死磕贪心最后超时”更稳。实际笔试中AC 是第一位代码优雅是第二位。6.3 一个容易踩的思维陷阱有人会想“我直接把所有大于 0 的菜选出来然后升序排不就行了”在[-1, 0, 5]这个用例上就会翻车。大于 0 的菜只有[5]总分 5但正确答案是[-1, 0, 5]总分 14。负菜的价值不是它本身而是它带来的“系数位移”。所以这道题不能用“只看正负”来筛选必须看边际收益。也有人会想“既然增量是S x那我是不是可以多次计算前缀和”可以但这其实就是贪心的另一种等价实现。你完全可以用两层循环枚举前缀长度再计算每个前缀反转后的加权和复杂度 O(n²)。增量贪心把这个过程压缩成了 O(n)是更漂亮的写法。7. 最后再分享一个小技巧把 Hard 题当成“讲证明题”来刷我刷题有一个习惯不管题目 AC 没 AC都会在题解区看一两条高赞思路找到那个“一句话证明”。对 1402 来说这句话就是“在队首插入一道值为 x 的菜收益等于当前已选总和加 x”。这句话比任何代码都重要。如果你在面试现场被问到这题可以按这样的节奏回答先说暴力不可行子集加排列的组合爆炸。再用交换论证说明排序性质大的在后面。然后给出增量公式S x 0。最后写代码并分析复杂度。这四步走完面试官大概率不会再追问代码细节。LeetCode 1402 的价值不在于“这道菜怎么做”而在于它帮你建立了一个很重要的解题直觉很多排列优化问题先把顺序定下来问题就瞬间从指数级变成线性级。把这个套路记牢比多刷十道模板题更值。
