LeetCode 1475简单栈
商品折扣后的最终价格 图解题解
这道题到底在问什么
prices = [8,4,6,2,3,9,5,1,7,5]。对每件商品，向右找第一个 ≤ 它的价当折扣，输出每件的最终价。
- 输入
- prices = [8,4,6,2,3,9,5,1,7,5]
- 输出
- [4,2,4,1,2,4,4,1,2,5]
最优解：一步一步想明白
- 3思路一句话：维护单调递增栈，栈顶贵就弹、弹出即定折扣、剩下的自己入栈等结账。一遍扫完 O(n)。下面一步步演给你看。
- 4轮到 prices[0] = 8，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 5没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 6轮到 prices[1] = 4，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 7当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
- 8没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 9轮到 prices[2] = 6，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 10没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 11轮到 prices[3] = 2，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 12当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
- 13当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
- 14没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 15轮到 prices[4] = 3，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 16没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 17轮到 prices[5] = 9，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 18没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 19轮到 prices[6] = 5，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 20当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
- 21没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 22轮到 prices[7] = 1，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 23当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
- 24当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
- 25当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
- 26没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 27轮到 prices[8] = 7，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 28没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 29轮到 prices[9] = 5，先看它能给栈里哪些更贵(或相等)的商品当折扣。
- 30当前价 ≤ 栈顶商品的价：栈顶等到了它的折扣，弹出并打折(原价 − 当前价)。继续看还能不能给更多商品打折。
- 31没人能再被它打折了（栈顶价 < 它或栈空），它自己入栈，单调递增结构保持。
- 32扫描结束，栈里残留的商品右边没有 ≤ 它的价，不打折，最终价就是原价。
- 33扫描结束，栈里残留的商品右边没有 ≤ 它的价，不打折，最终价就是原价。
⚠️ 容易写错的地方
✗ 错：对每件商品逐个往右暴力扫
✓ 对：维护单调递增栈一遍扫完
暴力 O(n²)，单调栈摊还 O(n)
✗ 错：折扣条件写成严格 > 漏了相等
✓ 对：栈顶价 ≥ 当前价就要弹(可相等)
题意是「小于等于」，相等也能当折扣
✗ 错：栈存价格而非下标
✓ 对：存下标，回填 res[j] 才定位得到
可能有重复价，靠下标才不串位
完整代码（Python / C++ / Java）
Python
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 resC++
vector<int> finalPrices(vector<int>& prices){
vector<int> res = prices; stack<int> st;
for(int i = 0; i < (int)prices.size(); i++){
while(!st.empty() && prices[st.top()] >= prices[i]){
int j = st.top(); st.pop();
res[j] = prices[j] - prices[i];
}
st.push(i);
}
return res;
}Java
class Solution {
public int[] finalPrices(int[] prices){
int[] res = prices.clone();
Deque<Integer> st = new ArrayDeque<>();
for(int i = 0; i < prices.length; i++){
while(!st.isEmpty() && prices[st.peek()] >= prices[i]){
int j = st.pop();
res[j] = prices[j] - prices[i];
}
st.push(i);
}
return res;
}
}复杂度
时间
O(n)
每件商品最多入栈、出栈各一次
空间
O(n)
单调栈最坏存全部下标
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 商品折扣后的最终价格 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么弹栈条件用「≥」、连相等也弹？+
折扣条件是右边第一个 prices[j] ≤ prices[i]（含相等）。栈顶价 ≥ 当前价就弹，弹完栈从底到顶递增；相等也弹才不漏。
和「下一个更小元素」是同一个模板吗？+
是。这题就是「每个元素右边第一个 ≤ 它的元素」，把答案从「那个元素」换成「原价 − 那个元素」即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 商品折扣后的最终价格 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。