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。再看 0，S + 0 = 5 > 0，加入 0，分数变成5 + 5 = 10，S = 5。再看 -1，S + (-1) = 4 > 0，加入 -1，分数变成10 + 4 = 14，S = 4。再看 -8，S + (-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(reverse=True) 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]来模拟：
| 当前菜品 x | cur_sum + x | 是否加入 | 更新后 ans | 更新后 cur_sum |
|---|---|---|---|---|
| 5 | 5 | 是 | 5 | 5 |
| 0 | 5 | 是 | 10 | 5 |
| -1 | 4 | 是 | 14 | 4 |
| -8 | -4 | 否，退出 | 14 | 4 |
3.2 C++ 实现
class Solution { public: int maxSatisfaction(vector<int>& 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 道菜时的最大分数。转移时，当前菜要么不选，要么作为第 j+1 道菜选进去。
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]) # 选当前菜，作为第 j+1 道菜 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，天然处理了什么菜都不做的情况。如果数组全是负数，降序排序后第一个数就小于等于 0，cur_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 > 0，0 也会被加入。
4.3 用>= 0会怎样
关于判断条件，我前面提到写> 0更标准。如果你写成>= 0，在大多数测试用例下也不会挂，因为cur_sum + x == 0说明当前增量是 0，加入后总分不变，但后面不会再出现正收益。不过面试时考官如果追问“等于 0 算有收益吗？”，你很难自洽。实战建议是严格使用> 0，少给自己挖坑。
4.4 排序方向不能搞反
我见过有人排序升序之后，从前往后扫，然后直接判断当前元素是否大于 0，这是错误解法。升序的正确做法是从后往前扫，或者转成降序再扫。逻辑核心是：从最大喜爱值开始尝试，而不是从最小开始。如果从最小开始，你根本不知道后面会不会有更大的菜来救它，增量公式的前提就变了。
为了减少出错，建议直接写成reverse=True或者rbegin()，让代码和推导过程一一对应。
4.5 边界用例速查表
| 输入 | 最优选择 | 分数 | 说明 |
|---|---|---|---|
[-1, -2, -3] | 不选 | 0 | 全负数 |
[0, 0, 0] | 不选或全选 | 0 | 0 不改变分数 |
[4, 3, 2] | [2,3,4] | 20 | 全正数，全部选 |
[-9, -8, -1, 0, 5] | [-1,0,5] | 14 | 负数可以垫系数 |
[0, 5] | [0,5] | 10 | 0 也有位移价值 |
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而不是s，ans而不是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 的价值不在于“这道菜怎么做”，而在于它帮你建立了一个很重要的解题直觉：很多排列优化问题，先把顺序定下来，问题就瞬间从指数级变成线性级。把这个套路记牢，比多刷十道模板题更值。
