1852. 最终优惠价(单调栈)

class Solution:
    """
    @param prices: a list of integer
    @return: return the actual prices
    """
    """
    大致思路:单调栈
    1.从右边开始往左边循环，依次放入栈里面，如果当前值 >= 栈右边第一个，则减去即可。如果当前值 < 栈右边第一个，则栈右边第一个pop掉，一直到符合条件的时候为止
    2.每次取出，写入res里面，最终返回res
    """
    def FinalDiscountedPrice(self, prices):
        # write your code here
        if len(prices) == 0:return 0 
        
        #初始化
        res,d = [prices[-1]],[prices[-1]]

        l = len(prices)
        for i in range(l - 2, -1,-1):
            if prices[i] >= d[0]:
                res.insert(0,prices[i] - d[0])
                d.insert(0,prices[i])
            else:
                while d != [] and prices[i] < d[0]:
                    d.pop(0)

                if d != []:
                    res.insert(0,prices[i] - d[0])
                else:
                    res.insert(0,prices[i])
                d.insert(0,prices[i])
    
        return res

class Solution:
    """
    @param prices: a list of integer
    @return: return the actual prices
    """
    """
    大致思路:单调栈
    1.从左边开始循环，如果当前价格出现小的，则替换，否则保持不变
    """
    def FinalDiscountedPrice(self, prices):
        #初始化
        res,d = [_ for _ in prices], []

        l = len(prices)
        for i in range(l):
            #后面出现小的，说明前面的值需要pop,res前面需要被替换了
            while d != [] and prices[i] <= prices[d[-1]]:
                print(d)
                index = d[-1]
                #前面的值需要被替换
                res[index] = prices[index] - prices[i]
                #pop前面大的,d [大，小 ，小，小，小]
                d.pop()

            d.append(i)

        return res