前阵子刷题，我在笔记里写下"leetcode1547：商品折扣后的最终价格"，结果点开题目列表一翻，1547根本不是这道题。真正对应"商品折扣后的最终价格"的是LeetCode 1475，而1547是另一道完全不同的区间DP题——切棍子的最小成本。这个题号错位看着像是手误，但它背后其实藏着一个很典型的问题：很多人刷题复习时只靠"题号+关键词"做锚点，一旦题号和题目对不上，记忆就直接崩了。
今天借这个机会，把1475这道题完整拆一遍。它本身是单调栈入门必刷的一道简单题，非常适合拿来理解"下一个更小元素"这个模型。我也会顺便讲讲，为什么它会被一堆人和1547弄混，以及真正的1547到底在考什么。不管你是在准备面试，还是刚开始刷数据结构，这篇应该都能给你一点实际帮助。
1. 一个题号引发的"记忆错位"：先搞清1475和1547到底差在哪
1.1 两张题目卡片先摆清楚
先把两题的基本信息列出来，看一眼就知道差异有多大：
| 对比项 | LeetCode 1475 | LeetCode 1547 |
|---|---|---|
| 中文名 | 商品折扣后的最终价格 | 切棍子的最小成本 |
| 英文名 | Final Prices With a Special Discount in a Shop | Minimum Cost to Cut a Stick |
| 难度 | 简单 | 困难 |
| 核心考点 | 数组 / 单调栈 | 数组 / 动态规划（区间DP） |
| 典型解法 | 反向遍历 + 单调递增栈 | 区间划分 + 状态转移 |
题目类型、难度、解法完全不在一个层级。一个是入门级单调栈，一个是需要重新排序切割点、再做区间合并的困难DP。如果只记住"1547 = 商品折扣"，那复习时翻到真正的1547，第一反应肯定是"这什么鬼"，然后开始怀疑自己之前到底刷没刷过。
1.2 为什么这两个题号会被记混
第一个原因是数字相近。1475和1547，只是数字排列顺序不同，视觉上非常容易混淆。第二个原因更隐蔽：不少刷题笔记、题解链接里不会完整写英文题目名，只写"LeetCode 1475 商品折扣"或者"1547 切棍子"，标题被压缩之后，记忆点就只剩一个模糊的关键词。
我自己复盘过这个错位，发现还有一个深层因素。1475的题干里有"最终价格"，1547的题干里有"成本"，两个词都跟"钱"有关。大脑在给题目打标签时，会把"价格/成本/折扣"归成同一类，于是题号相近加上语义相近，绑定就发生了。
这里想顺带提一个很实用的笔记习惯：不要只记题号，而是记录"题号 + 中文题名 + 一句话解法提示"。比如写"1475 商品折扣后的最终价格 / 反向单调栈，弹出比当前价格大的元素"。这样即使过几个月再翻笔记，也不用靠猜题号来回忆题目内容。我就是被这次错位提醒之后，才把所有刷题笔记统一改成了这种格式。
2. 重新读题："右侧第一个更小"和"右侧最小"是两码事
2.1 题干到底在说什么
原题描述很简短：给定一个整数数组 prices，代表商店里各商品的价格。对于每个商品 i，如果能找到一个下标 j，满足 j > i 且 prices[j] <= prices[i]，那么商品 i 的最终价格等于 prices[i] - prices[j]。如果找不到这样的 j，最终价格就保持原价。
注意，这里的 j 是"第一个满足条件的位置"，不是"后面所有商品中的最低价格"。这句话是这道题第一个容易踩的坑。
我拿一个具体例子跑一遍。假设 prices = [8, 4, 6, 2, 3]：
- i = 0，价格 8。从 i 右边开始找，第一个 <= 8 的是下标 1 的 4，所以最终价格是 8 - 4 = 4。
- i = 1，价格 4。右边第一个 <= 4 的是下标 3 的 2，最终价格是 4 - 2 = 2。
- i = 2，价格 6。右边第一个 <= 6 的是下标 3 的 2，最终价格是 6 - 2 = 4。
- i = 3，价格 2。右边没有比 2 更小或相等的元素，保持 2。
- i = 4，价格 3。右边没有元素，保持 3。
最终结果是 [4, 2, 4, 2, 3]。
2.2 一个典型的误读：找"右侧最小值"
如果审题不仔细，很容易把规则理解成"用右侧所有价格里的最小值来打折"。比如数组 [6, 5, 2, 8]，两种读法的差异就很明显：
| 商品 | 按"第一个 <= 当前" | 按"右侧最小值" |
|---|---|---|
| 6 | 右边第一个 <= 6 是 5，结果 1 | 右侧最小是 2，结果 4 |
| 5 | 右边第一个 <= 5 是 2，结果 3 | 右侧最小是 2，结果 3 |
| 2 | 右边没有 <= 2，结果 2 | 右侧最小是 8，2 <= 8 不成立，结果 2 |
| 8 | 右边没有元素，结果 8 | 结果 8 |
可以看到，第一个商品算出来的答案完全不同。题目里那句"下标 j 最小"是硬性条件，它决定的是"找到哪个折扣来源"，而不是"选一个最便宜的折扣来源"。
2.3 这种规则设计其实有现实直觉
你可以把它想象成排队结账时的优惠券。你手上拿着一张满减券，从你后面的商品开始一张一张看，遇到第一张可用的券就用它抵扣，不会越过前面的券去选后面一张面额更大的。按时间顺序遇到就生效，这就是"第一个满足条件"的生活化理解。想明白这一点，读题的时候就不容易跑偏。
3. 从暴力到单调栈：这道题的思考路径不是一步到位的
3.1 暴力解法：双层循环，直来直去
任何题目第一步都是先保证正确，再谈效率。简洁的双层循环可以这样写：
def finalPrices(prices): n = len(prices) res = prices[:] for i in range(n): for j in range(i + 1, n): if prices[j] <= prices[i]: res[i] = prices[i] - prices[j] break return res这个解法完全按照题意模拟，逻辑上没有任何问题。但它的问题也很明显：对于每个 i，都要向后扫描到第一个满足条件的位置，最坏情况下（数组单调递增，例如 [1, 2, 3, 4, 5]）每个 i 都要扫到数组末尾，总比较次数是 n + (n-1) + ... + 1，也就是 O(n^2)。当 n 到 10^5 级别时，10^10 次操作基本就跑不动了。
3.2 暴力重复做了哪些无用功
以 [8, 4, 6, 2, 3] 为例，暴力处理 i = 0 时，会依次看 4、6、2；处理 i = 1 时，会再看 6、2。也就是说，同一个元素会被反复比较。当扫描 i = 0 时，我们已经见过 6 和 2，并且知道 2 更小、也更靠后，但暴力没有把这个信息"记住"并传下去。
这个问题本质上是在做重复的线性查询：每次都要从当前位置往右重新询问"第一个满足条件的元素是谁"。如果一个结构能在处理完右侧之后，持续维护一份"候选答案集合"，每个元素只进出一次，那么总的复杂度就能降下来。单调栈就是干这个的。
3.3 换个方向：从右往左遍历
如果把遍历方向反过来，从数组末尾往开头走，情况会有趣很多。当处理到位置 i 时，右侧所有元素都已经"见过面"了。问题就变成：在已经见过的右侧元素里，找出离 i 最近的、且价格 <= prices[i] 的那个元素。
这时自然的想法是维护一个有序的候选序列。刚开始你可以用数组存右侧元素，每次线性扫一遍，但这跟暴力没有本质区别。后面要讲的核心就是：哪些右侧元素可以安全丢弃，剩下哪些才有资格当候选。
4. 单调栈里藏着的"遮蔽"逻辑：为什么可以放心弹出更大的数
4.1 先看最终代码怎么写的
def finalPrices(prices): n = len(prices) res = prices[:] stack = [] for i in range(n - 1, -1, -1): while stack and stack[-1] > prices[i]: stack.pop() if stack: res[i] = prices[i] - stack[-1] else: res[i] = prices[i] stack.append(prices[i]) return res这段代码用栈存的是价格值。栈的特性是：从栈底到栈顶单调递增，也就是栈顶是栈里最小的元素（或者说"离当前位置最近的可用候选"）。
处理每个位置 i 时，先弹出所有比 prices[i] 大的栈顶元素。弹完之后，如果栈里还有元素，那么栈顶就是我们要找的"右侧第一个 <= prices[i]"的折扣价。把当前价格减去栈顶，得到结果。最后把 prices[i] 入栈，供更左边的位置使用。
4.2 为什么栈顶的"大数"可以被弹出
这一节是单调栈最核心的原理。想象你从右往左走，右侧已经扫描过的位置里，有一个离你比较远的元素 a，它的价格是 10；现在面前来了一个离你更近的元素 b，价格是 5。换句话说，b 在 a 的左边，且 b <= a。
那 a 还有没有可能成为某个更左侧元素 x 的折扣来源呢？分两种情况看：
- 如果 x >= 5，那么 x 在往右找时，会先遇到 b，b 满足 <= x，所以答案轮不到后面的 a。
- 如果 x < 5，那么 x 一定也小于 10，a 同样不满足 <= x，所以 a 也不是答案。
无论哪种情况，a 都不可能再被用到了。这就是"遮蔽"：一个更近且更小的元素，会把远处更大的元素彻底淘汰。所以当 prices[i] 小于等于栈顶时，直接弹出栈顶，不需要犹豫。
如果当前元素比栈顶大呢？比如远处有个 2，眼前是 5，那么 5 不能弹掉 2。因为对左侧一个价格是 6 的元素来说，右边第一个 <= 6 的是 5，而不是 2。此时 5 是可能成为答案的，所以它保留入栈。这也正好保证了栈内从底到顶是单调递增的。
4.3 用手推一遍整个流程
还是用 [8, 4, 6, 2, 3]：
- i = 4，价格 3。栈空，结果 3，入栈 [3]。
- i = 3，价格 2。栈顶 3 > 2，弹出；栈空，结果 2，入栈 [2]。
- i = 2，价格 6。栈顶 2 <= 6，结果 6 - 2 = 4，入栈 [2, 6]。
- i = 1，价格 4。栈顶 6 > 4，弹出；栈顶 2 <= 4，结果 4 - 2 = 2，入栈 [2, 4]。
- i = 0，价格 8。栈顶 4 <= 8，结果 8 - 4 = 4，入栈 [2, 4, 8]。
最终输出 [4, 2, 4, 2, 3]，和暴力结果一致。每个元素最多入栈一次、出栈一次，总复杂度 O(n)，这也是单调栈这类题的共同特征。
5. 写代码前先盘清楚的三件事：边界、等号、以及要不要复制数组
5.1 第一个易错点：弹出条件是 > 还是 >=
题目要求的是 prices[j] <= prices[i]，也就是说"等于"也能作为折扣来源。假设 prices = [5, 5]，对于第一个 5，右边第一个 <= 5 的就是第二个 5，折扣价是 0，最终价格应该是 0。
所以在反向单调栈里，弹出条件是 while stack and stack[-1] > prices[i]，不是 >=。如果用 >=，遇到相等时会先把栈顶相等的价格弹出去，然后栈空，最终价格保持原价，结果就错了。
这一点看起来小，实际上很容易写顺手写错。建议记住一句话：等于也是一种合法答案，只有严格大于当前价格的元素才需要丢掉。
5.2 第二个易错点：要不要复制原数组
代码里我写了 res = prices[:]，没有直接改 prices。这是稳妥做法。有人会问：反向遍历的时候，处理完 prices[i] 之后，后面的遍历只访问更左边的位置，不会再看 prices[i]，那么原地修改 prices[i] 是不是也可以？
理论上可以，但我不推荐。原因有两个：一是原地修改会让代码意图变模糊，读者需要额外推理"这里为什么能改原数组"；二是如果之后想给题解加一个"记录折扣来源下标"的功能，保存一份原始数组会方便得多。与其在边界上钻牛角尖，不如一开始就复制一份，清爽又安全。
5.3 第三种写法：栈里存索引而不是值
很多讲"下一个更大/更小元素"的教程喜欢在栈里存数组下标，因为这样可以同时拿到值和位置。1475 这道题只要求返回最终价格，不要求返回来源下标，所以存值就够了。但为了和其他单调栈题目统一思路，存下标的写法同样常见：
def finalPrices(prices): n = len(prices) res = prices[:] stack = [] for i in range(n - 1, -1, -1): while stack and prices[stack[-1]] > prices[i]: stack.pop() if stack: res[i] = prices[i] - prices[stack[-1]] else: res[i] = prices[i] stack.append(i) return res两种写法核心逻辑完全一样，区别只在于栈里存什么。我个人建议初学者用"存索引"的版本，因为学到后面刷"每日温度""下一个更大元素"这类题时，索引栈可以直接复用同一套模板，减少切换成本。
5.4 从前往后的对称做法
反向遍历不是唯一选择。也可以从前往后遍历，用栈保存"还没找到折扣来源"的下标。当遇到一个新价格 x 时，把栈中所有价格 >= x 的下标依次弹出，并给它们赋值 prices[idx] - x。这个做法同样用掉了单调栈的"遮蔽"思想，只是把赋值动作推迟到了"找到答案"那一刻。
def finalPrices_forward(prices): n = len(prices) res = prices[:] stack = [] for i, x in enumerate(prices): while stack and prices[stack[-1]] >= x: idx = stack.pop() res[idx] = prices[idx] - x stack.append(i) return res这里弹出条件是 >=，因为从前往后看，只要遇到一个 <= 栈顶价格的新元素，栈顶就能确定折扣价。和反向版本正好镜像。两条路都通，面试时不用纠结哪条是"标准答案"，能讲清楚自己维护了什么、为什么弹出，就足够。
6. 顺着题号摸到1547：区间DP的世界和单调栈没有交集
6.1 真正的1547是什么
LeetCode 1547 是一道区间DP题。题目大意是：有一根长度为 n 的棍子，给定一个数组 cuts 表示允许切割的位置，每次切割的成本等于当前这一段棍子的长度，问按什么顺序切完所有指定位置，总成本最小。
题目的难点在于，切割顺序会影响中间每一段棍子的长度，从而影响成本。比如一根 10 长度的棍子，如果先在中点切成两段，第二次切某一段时成本是 5；如果先在某一段贴着端点切，第二次可能还要切接近 10 的长段。不同的顺序，总成本完全不同。
这类题需要先把 cuts 排序，然后在切割点之间做区间划分。核心状态可以定义为 dp[i][j]：表示切割区间内第 i 个切割点到第 j 个切割点之间的最小成本。状态转移时，枚举区间内最后一个切割点 k，把区间拆成两半，分别递归求解，再加上当前整段棍子的长度。朴素实现是 O(m^3)，m 是切割点数量，m 的范围通常不大，所以能过。
6.2 两道题放在一起，反而能帮你建立"题型锚点"
1475 和 1547 放在一起，最大价值其实是提醒你：刷题时不要只凭数字和印象标记题目，一定要给题目建一个"题型锚点"。
所谓锚点，就是"看到这个题名，第一秒能想到的算法标签"。1475 的锚点是"反向单调栈，等于也能打折"；1547 的锚点是"区间DP，先排序、再枚举切割顺序"。有了锚点之后，即使题号记错，至少不会把单调栈题当成区间DP来做。
我现在整理刷题笔记时，固定用这种格式：
- 题目：1475 商品折扣后的最终价格
- 一句话解法：反向遍历维护单调递增栈，弹出比当前价格大的元素，栈顶即折扣价
- 易错点：弹出条件是 > 不是 >=；记得复制数组
这样每道题复习成本很低，扫一眼就能把整套思路拉回来。这次被题号坑过的经历，也算一个反向教训，让我把笔记习惯彻底改掉了。
最后再分享一个小技巧。遇到这种"题号相近、语义相近"的题目时，我会把它们放到同一个收藏夹里，主动做一次对比，而不是试图靠脑子强行区分。写清楚两题的题干差异、考点差异、难度差异之后，反而记得更牢。1475 和 1547 就是个很好的对照组：一个简单，一个困难；一个用栈，一个用区间DP。把对照组记录下来，下一次再遇到相似题目，检索记忆就快多了。
