题目描述
思路解析动画文字版
思路一句话：维护单调递增栈，栈顶贵就弹、弹出即定折扣、剩下的自己入栈等结账。一遍扫完 O(n)。下面一步步演给你看。
轮到 prices[0] = 8，先看它能给栈里哪些更贵(或相等)的商品当折扣。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[1] = 4，先看它能给栈里哪些更贵(或相等)的商品当折扣。
当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[2] = 6，先看它能给栈里哪些更贵(或相等)的商品当折扣。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[3] = 2，先看它能给栈里哪些更贵(或相等)的商品当折扣。
当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[4] = 3，先看它能给栈里哪些更贵(或相等)的商品当折扣。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[5] = 9，先看它能给栈里哪些更贵(或相等)的商品当折扣。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[6] = 5，先看它能给栈里哪些更贵(或相等)的商品当折扣。
当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[7] = 1，先看它能给栈里哪些更贵(或相等)的商品当折扣。
当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[8] = 7，先看它能给栈里哪些更贵(或相等)的商品当折扣。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
轮到 prices[9] = 5，先看它能给栈里哪些更贵(或相等)的商品当折扣。
当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
扫描结束，栈里残留的商品右边没有 ≤ 它的价，不打折，最终价就是原价。
扫描结束，栈里残留的商品右边没有 ≤ 它的价，不打折，最终价就是原价。
边界先想清。
两个高频追问。
参考代码
def finalPrices(prices): res, stack = prices[:], [] for i, p in enumerate(prices): while stack and prices[stack[-1]] >= p: j = stack.pop() res[j] = prices[j] - p # 右边第一个 ≤ 它的价当折扣 stack.append(i) return res复杂度
- 时间：O(n)，每件商品最多入栈、出栈各一次
- 空间：O(n)，单调栈最坏存全部下标
易错点
面试追问把动画讲成自己的话
追问为什么弹栈条件用「≥」、连相等也弹？
追问和「下一个更小元素」是同一个模板吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
括号的最大嵌套深度
LeetCode 1614 · 简单 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题