前阵子刷题我在笔记里写下leetcode1547商品折扣后的最终价格结果点开题目列表一翻1547根本不是这道题。真正对应商品折扣后的最终价格的是LeetCode 1475而1547是另一道完全不同的区间DP题——切棍子的最小成本。这个题号错位看着像是手误但它背后其实藏着一个很典型的问题很多人刷题复习时只靠题号关键词做锚点一旦题号和题目对不上记忆就直接崩了。今天借这个机会把1475这道题完整拆一遍。它本身是单调栈入门必刷的一道简单题非常适合拿来理解下一个更小元素这个模型。我也会顺便讲讲为什么它会被一堆人和1547弄混以及真正的1547到底在考什么。不管你是在准备面试还是刚开始刷数据结构这篇应该都能给你一点实际帮助。1. 一个题号引发的记忆错位先搞清1475和1547到底差在哪1.1 两张题目卡片先摆清楚先把两题的基本信息列出来看一眼就知道差异有多大对比项LeetCode 1475LeetCode 1547中文名商品折扣后的最终价格切棍子的最小成本英文名Final Prices With a Special Discount in a ShopMinimum 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结果 45右边第一个 5 是 2结果 3右侧最小是 2结果 32右边没有 2结果 2右侧最小是 82 8 不成立结果 28右边没有元素结果 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 在往右找时会先遇到 bb 满足 x所以答案轮不到后面的 a。如果 x 5那么 x 一定也小于 10a 同样不满足 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。把对照组记录下来下一次再遇到相似题目检索记忆就快多了。 
长河君 · 2026/10/21 7:50:55 · 阅读 1.2k LeetCode 1475商品折扣与1547切棍子：单调栈和区间DP避坑指南
前阵子刷题我在笔记里写下leetcode1547商品折扣后的最终价格结果点开题目列表一翻1547根本不是这道题。真正对应商品折扣后的最终价格的是LeetCode 1475而1547是另一道完全不同的区间DP题——切棍子的最小成本。这个题号错位看着像是手误但它背后其实藏着一个很典型的问题很多人刷题复习时只靠题号关键词做锚点一旦题号和题目对不上记忆就直接崩了。今天借这个机会把1475这道题完整拆一遍。它本身是单调栈入门必刷的一道简单题非常适合拿来理解下一个更小元素这个模型。我也会顺便讲讲为什么它会被一堆人和1547弄混以及真正的1547到底在考什么。不管你是在准备面试还是刚开始刷数据结构这篇应该都能给你一点实际帮助。1. 一个题号引发的记忆错位先搞清1475和1547到底差在哪1.1 两张题目卡片先摆清楚先把两题的基本信息列出来看一眼就知道差异有多大对比项LeetCode 1475LeetCode 1547中文名商品折扣后的最终价格切棍子的最小成本英文名Final Prices With a Special Discount in a ShopMinimum 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结果 45右边第一个 5 是 2结果 3右侧最小是 2结果 32右边没有 2结果 2右侧最小是 82 8 不成立结果 28右边没有元素结果 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 在往右找时会先遇到 bb 满足 x所以答案轮不到后面的 a。如果 x 5那么 x 一定也小于 10a 同样不满足 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。把对照组记录下来下一次再遇到相似题目检索记忆就快多了。