How does a monotonic stack help solve the Final Prices With a Special Discount in a Shop problem?

A monotonic stack helps by maintaining an ordered sequence of indices that allows for efficient discount calculation, as we can quickly find the next smaller price to apply a discount.

What is the time complexity of the Final Prices With a Special Discount in a Shop problem?

The time complexity is O(n), as each item in the prices array is pushed and popped from the stack at most once, ensuring a linear time solution.

Can I solve the Final Prices With a Special Discount in a Shop problem using brute force?

Yes, brute force can be used by checking each item and searching for the next smaller price, but it would result in a time complexity of O(n^2), which is inefficient for large arrays.

What is the space complexity of the solution to the Final Prices With a Special Discount in a Shop problem?

The space complexity is O(n) due to the stack storing indices of the items as we traverse the prices array.

What are the potential pitfalls when solving the Final Prices With a Special Discount in a Shop problem?

Common pitfalls include forgetting to pop items from the stack correctly, not maintaining the stack's monotonic order, and not handling edge cases like when no discounts apply.

#1475

Easy

auto_awesome栈·状态

LeetCode 题解工作台

商品折扣后的最终价格

给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] 的最小下标，如果没有满足条件的 j ，你将没有任何折扣…

数组栈单调栈

题目描述

给你一个数组 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

lightbulb

解题思路

方法一：单调栈

题目实际上是求每个元素右侧第一个比它小的元素，可以使用单调栈来解决。

我们逆序遍历数组 $\textit{prices}$ ，利用单调栈找出左侧最近一个比当前元素小的元素，然后计算折扣。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{prices}$ 的长度。

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        stk = []
        for i in reversed(range(len(prices))):
            x = prices[i]
            while stk and x < stk[-1]:
                stk.pop()
            if stk:
                prices[i] -= stk[-1]
            stk.append(x)
        return prices

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidates should demonstrate an understanding of stack-based state management to handle the discount logic.
question_mark
Look for candidates who implement a monotonic stack to ensure the efficient calculation of discounts in linear time.
question_mark
Be aware of how well candidates can explain time and space complexity, particularly in terms of how the stack helps optimize the solution.

warning

常见陷阱

外企场景

error
Forgetting to pop elements from the stack when the price condition is met, which can result in incorrect discount calculations.
error
Not ensuring the stack maintains a monotonic order, leading to inefficient or incorrect solutions.
error
Failing to handle edge cases, such as when there are no discounts available for any items.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to apply discounts in reverse order (from last item to first), requiring a different stack management approach.
arrow_right_alt
Change the problem so that discounts are applied based on a percentage rather than a fixed price, requiring adjustments to how discounts are calculated.
arrow_right_alt
Introduce a scenario where discounts are limited to a certain number of items, requiring additional state management beyond a simple stack.

help

常见问题

外企场景

继续练习

#1504 统计全 1 子矩形 #1526 形成目标数组的子数组最少增加次数 #1574 删除最短的子数组使剩余数组有序