华为 OD 训练营 · 题解精讲
LC1475.商品折扣后的最终价格
题目描述
给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。 商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。 请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。 示例 1： 输入：prices = [8,4,6,2,3] 输出：[4,2,4,2,3] 解释： 商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。 商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。 商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。 商品 3 和 4 都没有折扣。 示例 2： 输入：prices = [1,2,3,4,5] 输出：[1,2,3,4,5] 解释：在这个例子中，所有商品都没有折扣。 示例 3： 输入：prices = [10,1,1,6] 输出：[9,0,1,6]
提示： 1 <= prices.length <= 500 1 <= prices[i] <= 10^3
题目解析
题目在说什么
这道题是让我们算商品打折后的最终价格。规则是这样的：你有一排商品，每个商品有一个原价。如果你买第 i 个商品，你可以享受一个折扣，这个折扣等于它后面某个商品的价格。但有个条件：那个后面的商品价格必须小于或等于当前商品的价格，并且要找到离你最近的那个（也就是下标最小的那个）。如果没有这样的商品，那就没有折扣，原价购买。
举个例子：价格是 [8,4,6,2,3]。
- 第0个商品价格8，它后面第一个小于等于8的是4（下标1），所以折扣是4，最终价格8-4=4。
- 第1个商品价格4，后面第一个小于等于4的是2（下标3），折扣2，最终价格4-2=2。
- 第2个商品价格6，后面第一个小于等于6的是2（下标3），折扣2，最终价格6-2=4。
- 第3个商品价格2，后面没有小于等于2的，所以没折扣，最终价格2。
- 第4个商品价格3，后面没有商品，也没折扣，最终价格3。
结果就是 [4,2,4,2,3]。
思路是怎么来的
想象你在逛超市，货架上有一排商品，每个商品标着原价。你想知道每个商品打折后多少钱。规则是：你买一个商品，可以拿它后面第一个比它便宜或一样便宜的商品价格当折扣。这就像你在排队结账，你前面的人（这里是你后面的商品）如果价格更低，你就可以用那个价格减掉一些钱。
怎么快速找到每个商品后面第一个小于等于它的价格呢？一个直观的想法是：从后往前看。因为你要找的是后面的商品，从后往前看，你就能知道后面已经有哪些价格了。比如，你从最后一个商品开始看，它后面没有商品，所以没折扣。然后往前看倒数第二个，它后面有最后一个商品，如果最后一个商品价格小于等于它，那就是折扣。再往前看倒数第三个，它后面有倒数第一和倒数第二两个商品，你需要找到第一个小于等于它的。
但这样每个商品都要往后扫描一遍，太慢了。有没有更聪明的方法？我们可以用一个“栈”来帮忙。栈就像一摞盘子，你只能从上面拿或放。我们可以把后面已经看过的价格按从小到大的顺序存进栈里，这样对于当前商品，我们只需要看栈顶（最上面的）价格是否小于等于它。如果栈顶太大，就把它丢掉（弹出），因为后面更小的价格才可能成为折扣。这样栈里始终保留着从当前往后看，那些可能成为折扣的候选价格。
这个思路的关键是：从后往前遍历，维护一个单调递增的栈（栈底到栈顶从小到大），这样栈顶就是当前商品后面第一个小于等于它的价格（如果有的话）。
代码逐步拆解
我们来看参考代码，一行一行解释。
int n = prices.length;
int[] ans = new int[n];- 先拿到数组长度 n，然后创建一个同样大小的结果数组 ans，用来存最终价格。初始值都是0。
Stack<Integer> stack = new Stack<>();- 创建一个栈，用来存价格。注意，栈里存的是价格数值，不是下标。
for (int i = n - 1; i >= 0; i--) {- 从最后一个商品开始往前遍历。为什么从后往前？因为我们要找的是后面的商品，从后往前看，我们就能知道后面已经有哪些价格了。
int p = prices[i];- 取出当前商品的原价 p。
while (!stack.isEmpty() && stack.peek() > p) {
stack.pop();
}