链接
https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/description/
思路:
单调栈
单调栈,顾名思义,就是在栈内,元素要么是单调递减的,要么是单调递增的。
这个题目要求我们找下一个更小的元素,所以这个栈应当是递增的。(即栈顶元素最大)而我们要找的是下一个更小的元素,所以要从后往前遍历prices。
单调栈的在线处理:我们在不断的生成单调栈的同时生成res。
代码
class Solution: def finalPrices(self, prices): mem = [] single_stack = [] for i in prices[::-1]: while len(single_stack) > 0: top = single_stack[-1] # 注意边界条件 if top > i: single_stack.pop() else: break if len(single_stack) == 0: top = 0 else: top = single_stack[-1] mem.append(i-top) single_stack.append(i) return mem[::-1]
标签:mem,折扣,最终,top,single,1475,prices,stack,单调 From: https://www.cnblogs.com/bjfu-vth/p/17746144.html