LeetCode 1475. 商品折扣后的最终价格
目录
题目描述
题意分析
给一个价格数组
prices。买第i件商品时，可以获得一份折扣：折扣额等于prices[j]，其中j是满足j > i且prices[j] <= prices[i]的最小下标。如果不存在这样的j，就没有折扣。要求返回每件商品折扣后的实际支付价格数组。
两个限定词必须同时抠死。「最小下标」意味着只取右边第一个符合条件的，不是最小的那个价格，也不是任意一个；「
<=」意味着相等也算，这一点和大多数「下一个更大/更小元素」题里的严格不等号不同，写错会让相同价格的商品拿不到折扣。
折扣是一次性的减法，不是打折率，也不会叠加：结果就是
prices[i] - prices[j]。由于条件里prices[j] <= prices[i]，结果一定非负，不用担心出现负价格。
约束里
prices.length <= 500，$O(n^2)$ 的双重循环稳过。所以这道题被归为「简单」。但它出现在面试里的意义完全不在于能不能过，而在于能不能认出这是「下一个更小或相等元素」的模板题并写出 $O(n)$ 的单调栈——面试官问这题，等的就是这个词。
边界：最后一件商品右边没有任何元素，必然没有折扣；数组严格递增时每件商品右边都没有更小或相等的，全部无折扣；数组元素全部相同时，除最后一件外每件都能拿到等于自身的折扣，结果全是 0。
解法：单调栈寻找右侧首个不大于元素
核心思路
暴力解是对每个
i向右扫描，遇到的第一个prices[j] <= prices[i]就是折扣来源，$O(n^2)$。观察这个过程会发现大量重复：如果prices[3]向右走了很远才找到答案，prices[4]、prices[5]很可能又要沿着同一段路再走一遍。
换个视角能看清结构。把暴力的「对每个
i找它的j」反过来，变成「对每个j，它能为哪些还没找到折扣的i结算」。当我们从左到右扫描到位置j时，左边那些还没找到折扣的下标里，凡是prices[i] >= prices[j]的，答案就都是j——因为j是它们向右遇到的第一个不大于自己的元素。
关键在于：这些「还没找到折扣的下标」在栈里天然是价格单调递增的（从栈底到栈顶）。为什么？因为一旦某个新元素小于等于它前面的某个待定元素，那个待定元素立刻就被结算并出栈了，留在栈里的必然是「一路严格递增」的一串。于是不变量可以写成：栈中自底向上保存的是尚未找到折扣的下标，且它们对应的价格严格递增。
有了这条不变量，扫描到
j时只需要不断检查栈顶：只要prices[stack.top] >= prices[j]，就说明栈顶这件商品找到了它的折扣，弹出并写答案res[top] = prices[top] - prices[j]；直到栈顶价格严格小于prices[j]为止（此时栈里剩下的都更小，j帮不了它们）。然后把j自己压栈，等待后面的元素来结算它。
因为每个下标只入栈一次、出栈一次，总操作数是 $O(n)$。扫描结束后仍留在栈里的下标就是「右边找不到更小或相等元素」的商品，它们没有折扣——只要一开始把结果数组初始化成
prices的副本，这批就不需要任何额外处理。
解题步骤
- 结果数组初始化为
prices的副本：默认「无折扣」。这样扫描结束后栈里的残留元素自动保留原价，也避免修改调用方传入的数组。原地结算同样能做对，但这里选择副本让输入与输出职责更清晰。- 栈里存下标而不是价格：结算时既要写
res[idx]，又要读prices[idx]，只存价格就丢了位置信息。这是单调栈题的通用选择。- 从左到右遍历
i：把i当作「可能为左侧待定元素提供折扣」的候选。- 弹栈条件用
>=而不是>：prices[stack.top] >= prices[i]时结算。题目条件是prices[j] <= prices[i]，等价于「栈顶价格 ≥ 当前价格」，相等必须算进去。- 弹栈时立刻写答案：
res[idx] = prices[idx] - prices[i]。用prices而不是res取原价——res[idx]此刻还是原价没错，但语义上折扣是基于原价计算的，读prices更不容易在改写代码时踩坑。- 弹完再把
i压栈：顺序不能反。先压栈会让i和自己比较（prices[i] >= prices[i]恒成立），把自己弹出并结算成res[i] = 0，全盘皆错。- 循环结束直接返回
res：栈里的残留就是无折扣商品，副本初始化已经处理好了。
以
prices = [8, 4, 6, 2, 3]走一遍。初始res = [8, 4, 6, 2, 3]，栈为空。
i = 0（价格 8）：栈空，无可结算。压入 0。栈 =[0]（价格视图[8]）。
i = 1（价格 4）：栈顶下标 0 的价格 8 >= 4，结算res[0] = 8 - 4 = 4，弹出。栈空，停止。压入 1。栈 =[1]（[4]）。
i = 2（价格 6）：栈顶下标 1 的价格 4 >= 6？不成立，不弹。压入 2。栈 =[1, 2]（[4, 6]，自底向上递增，符合不变量）。
i = 3（价格 2）：栈顶下标 2 的价格 6 >= 2，结算res[2] = 6 - 2 = 4，弹出。新栈顶下标 1 的价格 4 >= 2，结算res[1] = 4 - 2 = 2，弹出。栈空，停止。压入 3。栈 =[3]（[2]）。
i = 4（价格 3）：栈顶下标 3 的价格 2 >= 3？不成立，不弹。压入 4。栈 =[3, 4]。
遍历结束，栈里残留下标 3 和 4，它们右边没有更小或相等的价格，保持原价 2 和 3。
返回
res = [4, 2, 4, 2, 3]，与期望一致。注意i = 3那一步一次弹出了两个元素——这正是单调栈相对暴力的收益来源：下标 1 和 2 各自向右的搜索被合并进了同一次弹栈。
再用
prices = [10, 1, 1, 6]检验>=的必要性：i = 2（价格 1）时栈顶是下标 1 的价格 1，1 >= 1成立，结算res[1] = 1 - 1 = 0。若弹栈条件写成>，下标 1 拿不到折扣，输出[9, 1, 1, 6]，而正确答案是[9, 0, 1, 6]。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int[] finalPrices(int[] prices) {
// 先按「无折扣」初始化，扫描结束后仍在栈里的元素自动保留原价。
int[] res = prices.clone();
// 栈里存下标：结算时既要写 res[idx] 又要读 prices[idx]。
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < prices.length; i++) {
// 条件是 prices[j] <= prices[i]，相等也要算，所以弹栈用 >=。
while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
int idx = stack.pop();
res[idx] = prices[idx] - prices[i];
}
// 必须弹完再压，否则自己会把自己结算成 0。
stack.push(i);
}
return res;
}
}
func finalPrices(prices []int) []int {
// 先按「无折扣」初始化，扫描结束后仍在栈里的元素自动保留原价。
res := make([]int, len(prices))
copy(res, prices)
// 栈里存下标：结算时既要写 res[idx] 又要读 prices[idx]。
stack := []int{}
for i, price := range prices {
// 条件是 prices[j] <= prices[i]，相等也要算，所以弹栈用 >=。
for len(stack) > 0 && prices[stack[len(stack)-1]] >= price {
idx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res[idx] = prices[idx] - price
}
// 必须弹完再压，否则自己会把自己结算成 0。
stack = append(stack, i)
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$。外层遍历
n次；内层while看似嵌套，但每个下标一生只入栈一次、出栈一次，所有弹栈操作加起来不超过n次，因此总操作是 $O(n)$ 而非 $O(n^2)$。这个「均摊」论证是单调栈题被追问时的标准答法，务必能讲清楚。- 空间复杂度：$O(n)$。栈最坏存下全部下标（数组严格递增时没有任何元素被弹出）；结果数组是题目要求的输出，另计 $O(n)$。相比 $O(n^2)$ 时间的暴力，这是用线性空间换来的线性时间。
关键点总结
- 认出题型比写对代码更重要：「右边第一个满足某种大小关系的元素」是单调栈的标准触发词。本题的变体是「不大于」（含等于），对应弹栈条件
>=。面试时先说出「这是下一个更小或相等元素问题」，再动手写，节奏会好很多。- 视角反转是单调栈的思想内核：从「我去找我的答案」改成「我来为之前的人结算答案」。想清楚这一点，弹栈时机、栈内单调性、以及为什么是 $O(n)$ 就全都通了。
- 不变量要能一句话说出来：栈内自底向上下标递增、价格严格递增，且都是尚未确定答案的元素。被问「栈里存的是什么」时，这就是标准答案。
- 严格与非严格的选择直接由题面决定：本题是
prices[j] <= prices[i]，所以弹栈用>=。改成严格小于就要用>。这一个符号是本题唯一的语义陷阱。- 结果数组预填原值，把「找不到答案」的情况变成不需要处理的默认态。这个技巧在 496、739 等题里同样适用（那里是预填 -1 或 0）。
- 先弹后压，且栈存下标。两条都是模板级别的固定动作，写反任何一条都会得到系统性错误。
易错点总结
- 弹栈条件写成
>而不是>=：prices = [10, 1, 1, 6]时下标 1 遇到相等的价格 1 不会被结算，输出[9, 1, 1, 6]，正确答案是[9, 0, 1, 6]。- 先压栈再弹栈：
i刚入栈就满足prices[i] >= prices[i]，立刻把自己弹出结算成res[i] = 0，prices = [8, 4, 6, 2, 3]会输出全 0。res初始化为全 0：栈里残留的无折扣商品最终留下 0 而不是原价，prices = [1, 2, 3, 4]（严格递增，全部无折扣）会输出[0, 0, 0, 0]，正确答案是[1, 2, 3, 4]。- 栈里存价格而不是下标：弹栈时知道被结算的价格却不知道该写进
res的哪一格，只能退回额外维护映射，重复价格时映射还会冲突。- 循环结束后又对栈内残留做一次结算：把栈里剩下的下标减去某个默认值（如 0 或最后一个元素），
prices = [1, 2, 3]会把 2 和 3 错误折扣掉，正确行为是原价保留。- 误以为要找「右边最小的价格」而不是「右边第一个不大于的价格」：
prices = [8, 4, 6, 2, 3]中下标 0 会被折扣成8 - 2 = 6，而正确答案是8 - 4 = 4。题目要的是最小下标，不是最小价格。- Go 里弹栈时忘记先取出
idx就截断切片：先执行stack = stack[:len(stack)-1]再读stack[len(stack)-1]，拿到的是下一个元素，结算对象整体错位一位。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 496. 下一个更大元素 I | 简单 | 方向相反（找更大），还要额外用哈希表把结果映射回子集查询 |
| 503. 下一个更大元素 II | 中等 | 数组是环形的，需要遍历两遍或对下标取模来模拟绕回 |
| 739. 每日温度 | 中等 | 要的是下标之差而非值之差，找不到时补 0，是「下一个更大元素」的裸模板 |
| 901. 股票价格跨度 | 中等 | 在线数据流场景，栈中需合并已弹出元素的跨度，考察设计与单调栈的结合 |
| 42. 接雨水 | 困难 | 弹栈时要同时用到左右两个边界来计算面积，是单调栈的「横向结算」变体 |
| 84. 柱状图中最大的矩形 | 困难 | 需要同时求左右两侧第一个更小元素，常配合哨兵简化边界处理 |