LeetCode 1475简单栈
商品折扣后的最终价格 图解题解
这道题到底在问什么
给你一个数组 prices，其中 prices[i] 是第 i 件商品的价格。买第 i 件商品时，可以得到 prices[j] 的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的最小下标；如果不存在这样的 j，就没有折扣。返回每件商品折扣后最终需要支付的价格。
- 输入
- prices = [8,4,6,2,3]
- 输出
- [4,2,4,2,3]
- 解释
- 8 的第一个可用折扣是 4；4 和 6 的第一个可用折扣都是 2；2 和 3 没有折扣。
- 输入
- prices = [1,2,3,4,5]
- 输出
- [1,2,3,4,5]
- 输入
- prices = [10,1,1,6]
- 输出
- [9,0,1,6]
先想最直接的笨办法
暴力法的关键动作是“等右边第一个不更贵的价格”。单调栈会把这些还没等到折扣的下标先存起来。（动画第 3 步）
最优解：一步一步想明白
- 3暴力法的关键动作是“等右边第一个不更贵的价格”。单调栈会把这些还没等到折扣的下标先存起来。
- 4不变量：栈里的下标都还没拿到折扣；从左到右扫描保证当前 price 是它们遇到的第一个右侧候选。
- 5执行：ans = prices[:]; stack = []如果某件商品最后没有折扣，答案就保持原价。所以先复制一份 prices 到 ans。
- 6while 不成立；执行 stack.append(i)第一件商品 8 还没有看到右边的商品，先把下标 0 压栈，等后面来一个 <=8 的价格。
- 7执行：ans[stack.pop()] -= price当前 4 是下标 0 右边遇到的第一个 <=8 的价格，所以 8 的折扣立刻确定，不能继续往后找 2。
- 8执行：stack.append(i)结算完别人后，当前商品 4 也可能在右边找到折扣，所以把下标 1 压入栈。
- 9while stack and prices[stack[-1]] >= price 不成立价格 6 比栈顶 4 贵，不能作为 4 的折扣。它自己还没找到折扣，所以压栈等待。
- 10执行：ans[stack.pop()] -= price当前 2 是下标 2 右侧第一个 <=6 的价格，所以商品 2 的最终价格变成 4。
- 11while 继续成立：prices[1] >= 2一个当前价格可能连续给多个旧商品打折。因为 2 也是下标 1 右侧第一个 <=4 的价格，所以继续弹栈结算。
- 12执行：stack.append(i)2 已经帮别人结算完，但它自己仍要等右边有没有 <=2 的价格。
- 13while 不成立；执行 stack.append(i)3 比 2 贵，不能作为商品 3 的折扣。把 4:3 压栈后，扫描就结束了。
- 14执行：return ans栈里剩下的下标一直没等到右侧 <= 自己的价格，答案保持原价。最终返回 [4,2,4,2,3]。
- 17单调栈不是背模板，而是把“未来第一个满足条件的人”变成“当前元素解决栈顶的一批等待者”。
⚠️ 容易写错的地方
✗ 错：while 条件写成 prices[stack[-1]] > price
✓ 对：必须写 >=
题目允许 prices[j] <= prices[i]，相等价格也能作为折扣。
✗ 错：栈里只存价格
✓ 对：栈里存下标
要修改 ans[某个下标]，只存价格找不回位置。
✗ 错：当前 price 只弹一次
✓ 对：用 while 连续弹出所有可结算下标
同一个价格可能同时成为多个旧商品的第一个折扣。
✗ 错：给 8 选择后面的 2 作为折扣
✓ 对：选择最小下标的 4
题目要求第一个满足条件的位置，不是最便宜的位置。
完整代码（Python）
Python
class Solution:
def finalPrices(self, prices):
ans = prices[:]
stack = []
for i, price in enumerate(prices):
while stack and prices[stack[-1]] >= price:
ans[stack.pop()] -= price
stack.append(i)
return ans复杂度
时间复杂度
O(n)
每个下标最多入栈一次、出栈一次。
空间复杂度
O(n)
最坏情况下价格递增，所有下标都会留在栈中。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 商品折扣后的最终价格 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「栈」，换最直接的暴力解会差在哪？+
栈抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。