不知道有没有更好的解法~

zzzrf 1月前 22

原题直接看这里吧~

我就写了一种解法。也不知道是不是最优解。大家帮忙看看~

解释:

每一个物品都保持原价,他们的右边都没有等于或者更低价格的物品

单调非递减栈来存储之前的值,当出现比栈顶所存值更小的值则可以更新之前的价格。

代码

class Solution:
    """
    @param prices: a list of integer
    @return: return the actual prices
    """
    def FinalDiscountedPrice(self, prices):
        # write your code here
        s, res = [], [prices[i] for i in range(len(prices))]

        for i in range(len(prices)):
                while len(s) != 0 and prices[s[-1]] >= prices[i]:
                        index = s[-1]
                        s.pop()
                        res[index] = prices[index] - prices[i]
                s.append(i);
        return res
最新回复 (0)
  • 游客
    2
返回