以下两题都是使用双向队列来维护一个非递增的序列，序列的第一个值为当前可取范围的最大值，这样可以将找最大值的时间复杂度由O(n)降到O(1)。
面试题59 - I. 滑动窗口的最大值
题目
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
题解
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums:
return []
n = len(nums)
deque = collections.deque([])
res = []
for i, j in zip(range(1-k,n+1-k),range(n)):
while deque and deque[-1]<nums[j]:
deque.pop()
deque.append(nums[j])
if i>=0:res.append(deque[0])
if i>=0 and deque[0]==nums[i]:
deque.popleft()
return res
时间复杂度：O(n)，每个元素最多仅入队和出队一次，O(2n)
空间复杂度：O(k)，因为双向队列中最多同时存储 k 个元素
注意点：
- 使用zip的操作，可以同时遍历左右节点
- 注意双向队列中何时进行入队和出队
面试题59 - II. 队列的最大值
题目
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
题解
class MaxQueue:
def __init__(self):
self.temp=collections.deque([])
self.deque=collections.deque([])
def max_value(self) -> int:
if not self.temp:
return -1
return self.deque[0]
def push_back(self, value: int) -> None:
self.temp.append(value)
while self.deque and self.deque[-1]<value:
self.deque.pop()
self.deque.append(value)
def pop_front(self) -> int:
if not self.temp:
return -1
pop_value = self.temp.popleft()
if pop_value ==self.deque[0]:
self.deque.popleft()
return pop_value
时间复杂度：O(1)，仅有插入、删除、求最大值的操作
空间复杂度：O(n)，需要用队列存储所有插入的元素
注意点：
- 注意双向队列中的应用