python 商品折扣后的最终价格(leetcode)

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

解法一

• 思路遍历找到该数，然后减去折扣。
  代码如下：

class Solution:
    def finalPrices(self, prices):
        res = []
        length = len(prices)
        for i in range(length):
            for j in range(i + 1, length):
                if prices[j] <= prices[i]:
                    res.append(j)
                    break
            else:
                res.append(-1)
        return [prices[i] - (prices[res[i]] if res[i] != -1 else 0) for i in range(length)]

解法二

• 利用栈的单调性

class Solution01:
    def finalPrices(self, prices):
        lessNum = {}
        length, stack = len(prices), []
        for index, num in enumerate(prices):
            # 栈是单调递减的
            while stack and stack[-1][1] >= num:  # [][1] 取到的是值。栈顶的元素遇到了比自己小的第一个数，
                lessNum[stack.pop()] = num # 记录当前的数，并且弹出栈
            # 当前数比栈顶的数大，入栈，所以栈就保持了单调递减
            stack.append((index, num))
        return [num - lessNum.get((index, num), 0) for index, num in enumerate(prices)]