商品折扣后的最终价格

标签: 栈 数组 单调栈

难度: Easy

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

Submission

运行时间: 22 ms

内存: 16.1 MB

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        ans = []
        # for i in range (len(prices)):
        #     ans.append(prices[i])
        #     for j in range (i+1,len(prices)):
        #         if prices[j]<=prices[i]:
        #             ans.pop()
        #             ans.append(prices[i]-prices[j])
        #             break
        # return ans

        ans = prices[:]
        stack = []
        for i in range(len(prices) - 1, -1, -1):
            while stack and prices[i] < prices[stack[-1]]:
                stack.pop()
            if stack:
                ans[i] = prices[i] - prices[stack[-1]]
            stack.append(i)
        return ans

Explain

题解使用了栈的方法来解决问题，该方法非常适用于处理‘下一个更小或者相等元素’的问题。首先，创建一个栈来存储商品的下标，这样可以利用栈的特性来追踪和比较商品的价格。遍历商品的价格列表，从最后一个元素开始向前遍历。在遍历过程中，如果当前商品的价格小于栈顶商品的价格，则将栈顶元素出栈，这是因为栈中应只保留可能为后续元素提供折扣的商品下标。如果栈不为空，则说明找到了当前商品可以享受的折扣，否则该商品不享受折扣。最终，计算的结果直接更新在结果列表中，避免了使用额外的空间。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        ans = prices[:]  # 创建答案数组，初始化为原始价格
        stack = []  # 创建一个空栈以存放商品的下标
        for i in range(len(prices) - 1, -1, -1):  # 从后向前遍历
            while stack and prices[i] < prices[stack[-1]]:  # 当栈不空且当前价格小于栈顶价格时
                stack.pop()  # 弹出栈顶元素
            if stack:  # 如果栈不为空，则说明找到了可用的折扣
                ans[i] = prices[i] - prices[stack[-1]]  # 应用折扣
            stack.append(i)  # 将当前商品的下标推入栈中
        return ans  # 返回最终的折扣后价格列表

Explore

栈是一种后进先出（LIFO）的数据结构，这种特性使得栈非常适合于处理类似于'下一个更小或者相等元素'的问题。在本题中，栈被用来存储商品的下标，而不直接存储商品价格，这使得我们能够保持对商品价格的索引和顺序的追踪。在从右向左遍历价格列表的过程中，我们将当前商品的价格与栈顶的商品价格进行比较：如果栈顶价格高于或等于当前商品的价格，则栈顶商品的下标会被保留在栈中，因为它可能为之后的商品提供折扣；如果栈顶价格低于当前价格，则该栈顶商品无法为任何后续商品提供折扣，因此被移除。这样，栈总是保持了一个从栈底到栈顶价格递减的顺序，便于快速查找到下一个更小或相等的价格。

从后向前遍历商品价格列表的主要优势在于，这样可以在遍历的同时直接找到每个商品的'下一个更小或者相等的价格'。如果从前向后遍历，当我们处理每个商品时，我们还不知道其后面商品的价格，因此无法直接确定是否存在折扣以及折扣的具体金额。从后向前遍历使得我们在处理每个商品时，栈中已经包含了该商品之后的所有商品的信息，这样可以直接判断并应用折扣。

当当前商品的价格小于栈顶商品的价格时，栈顶商品不能为当前商品或任何在当前商品之前的商品提供折扣，因为它的价格高于当前考察的商品。因此，这样的栈顶元素对于后续操作没有用处，应该被出栈以维护栈内的有效性和秩序。出栈操作确保栈中始终保留那些可能对后续商品有用（能提供折扣）的商品下标。这样做可以优化算法的执行效率，减少不必要的比较。

如果栈为空，这意味着在当前商品之后没有任何商品的价格小于或等于当前商品的价格。因此，当前商品不能享受任何折扣。在这种情况下，商品的最终价格就是其原始价格。算法直接使用原始价格更新结果列表，不进行任何减价操作。