原题直接看这里吧~

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

解释:

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

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

代码

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)