单调队列是求解区间最大值或最小值的算法
正向遍历时，是先入后出 , 队列中的下标是按照从左往右递增 , 由于正向遍历，当前下标比之前下标大，所以与末尾值比较 ， 并且入列时添加在末尾 , 出列弹出队首
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:# 求解区间最大值q = deque([])ans = []for i , num in enumerate(nums):# 入列while q and nums[q[-1]] <= num:q.pop()q.append(i)# 超出区间 出列if i - q[0] + 1 > k:q.popleft()if i >= k - 1:ans.append(nums[q[0]])return ans
反向便利时，是先出后入，队列中的下标也是按照从左往右递增 ，由于反向遍历 ， 当前下标比之前下标小，所以与队列首位比较 ， 并且入列时添加在首位 ， 出列弹出队尾
class Solution:def minimumCoins(self, prices: List[int]) -> int:n = len(prices)q = deque([(n+1,0)])for i in range(n,0,-1):while q and q[-1][0] > 2 * i + 1:q.pop()f = q[-1][1] + prices[i-1]while q and q[0][1] >= f:q.popleft()q.appendleft((i,f))return q[0][1]
