LeetCode 1475. 商品折扣后的最终价格

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节
标签
数组 栈 单调栈

题目描述

✅ 1475. 商品折扣后的最终价格

image-20260929084832644

image-20260929084832726

题意分析

对每件商品，在它右侧寻找第一件价格小于或等于其原价的商品，并用这个价格作为折扣。最终价格为当前原价减去折扣；如果右侧没有符合条件的商品，就保持原价。

“第一件”按下标先后决定，不是寻找右侧最低价。相同价格也能触发折扣，得到零是合法结果。所有判断都使用原始价格，不能让其他商品打折后的新价格参与后续比较。

解法：单调栈寻找右侧首个不大于元素

核心思路

[!blue]

如果逐件向右搜索，很多位置会被反复检查。改为从左向右扫描：读到当前价格时，为左侧仍在等待、且原价不低于它的商品直接确定折扣。用栈保存这些尚未找到答案的商品下标，便于写回各自结果位置。

栈中下标对应的原价从栈底到栈顶严格递增。当前价格不大于栈顶原价时，弹出该下标并计算折后价，再继续判断新的栈顶。当前价格可能同时为多个等待商品提供折扣，所以必须持续弹出，而不是只处理一个。

被弹商品此前一直留在等待栈中，说明从它到现在还没有出现过符合条件的右侧价格。扫描顺序又是从左到右，因此当前商品就是它右侧第一件不更贵的商品，折扣一旦确定就不需要再考虑更远位置。

当栈顶原价已经小于当前价格，栈中更靠下的价格只会更小，同样不符合打折条件，可以停止弹栈。随后把当前下标入栈，等待未来商品来确定它的折扣；弹完再压，也避免当前商品与自己匹配。

答案数组先复制全部原价，只在找到折扣时修改对应结果。扫描完仍在栈中的商品没有任何合适折扣，保留初始原价即可；原始价格数组保持不变，用于后续所有比较。

解题步骤

  1. 复制原价格数组作为结果，准备保存待处理下标的空栈。
  2. 从左到右扫描当前商品，只要栈顶原价大于或等于当前原价，就弹出栈顶。
  3. 为弹出的商品写入“该商品原价减当前原价”，继续处理其他符合条件的栈顶。
  4. 弹栈结束后将当前下标入栈。
  5. 扫描完成返回结果，尚未弹出的下标自动保留原价。

代码实现

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++) {
            // 栈顶原价不小于当前价时结算折扣，相等价格也符合条件。
            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 {
        // 栈顶原价不小于当前价时结算折扣，相等价格也符合条件。
        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)。每个下标入栈一次、最多出栈一次，全部内层弹栈次数不超过商品数。
  • 空间复杂度：O(n)。单调栈最多保存全部下标，结果数组也需要线性空间。

关键点总结

[!green]

  • 栈记录尚未遇到合适折扣的位置，“第一个”由等待状态和扫描顺序共同保证。
  • 相等原价也满足条件，因此弹栈比较包含等号。
  • 栈存下标而不是只有价格，才能把答案写回对应商品。
  • 原价与结果分开保存，避免打折后的值污染判定。

易错点总结

[!yellow]

  • 寻找右侧最低价：题目只使用第一件符合条件的商品，更远的更低价不应替换它。
  • 比较条件写成严格大于：相同价格可以打折，不能漏掉等号。
  • 每轮只弹一个下标：当前商品可能同时解决多个等待位置，需使用循环。
  • 先把当前下标入栈再匹配：当前值会满足与自身相等的条件，错误地把自己当折扣。
  • 用已经打折的结果比较：折扣规则依赖原价，需要保留原始价格。
  • 给未找到折扣的位置保留默认零值：无折扣时应该返回原价，结果应先复制原数组。

相似题目

题目 难度 关联与区别
496. 下一个更大元素 I 简单 同样找右侧第一个满足大小关系的值，本题要求小于等于，且输出原价减去该值。
739. 每日温度 中等 单调栈的待匹配下标结构相同，原题找严格更大并返回距离，本题找不大于的折扣值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/93609742
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！