Uber OA 商品折扣：右侧首个不高于原价的价格

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 价格为非负整数；第 i 件商品减去其右侧第一个价格 ≤prices[i] 的商品价格，若不存在则无折扣。
• 返回每件商品的最终售价与总和；题目主要要求总花费，逐件结果仅方便解释与校验。
• 每件商品独立寻找折扣，不因前一件商品用过某价格就消耗右侧商品。

解题路线

1. 从左到右扫描，用栈保存尚未遇到折扣的商品下标，并使对应价格严格递增。
2. 看到新价格 p 时，连续弹出栈顶价格 ≥p 的下标。由于此前扫描范围内没有合格折扣，p 正是这些商品右侧第一个合格价格。
3. 把 p 从被弹出商品的最终售价中扣除；扫描后仍在栈内的商品保持原价，最后求和。

手动走一遍

[2,3,1,2,4,2] 的右侧首个合格折扣依次为 [1,1,0,2,2,0]，逐件售价 [1,2,1,0,2,2]，总花费 8。等价价格也必须触发折扣，例如 [4,4] 的结果是 [0,4]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Final price after the first no-greater price to the right."""


def final_prices(prices: list[int]) -> tuple[list[int], int]:
    if any(price < 0 for price in prices):
        raise ValueError("prices must be nonnegative")
    result = prices.copy()
    pending: list[int] = []
    for j, price in enumerate(prices):
        while pending and prices[pending[-1]] >= price:
            i = pending.pop()
            result[i] -= price
        pending.append(j)
    return result, sum(result)

复杂度

每个下标至多入栈、出栈各一次，时间 O(n)；结果与栈占 O(n) 空间。若只要总和也仍需保存待折扣商品及原价/下标。

易错点与追问

容易失分的边界

• 条件是小于等于；使用严格小于会漏掉等价商品。
• 找全局右侧最小价不等于找第一个合格价；顺序不能忽略。
• 若题目只给总花费，计算时仍要区分无折扣与价格恰好为 0 的折扣；二者售价相同但解释不同。

继续深挖

• 若要返回原价售出下标，扫描后栈中剩余下标按升序输出； 题目将其作为额外输出。若要折扣来源下标，弹栈时记录当前 j。
• 若商品流不断追加，单调栈可增量维护尚未结算商品，但总价在未来追加时可能变化，需声明查询语义。