class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if len(nums) < k:
return None
res = []
for i in range(k, len(nums)+1):
res.append(max(nums[i-k: i]))
return res
时间复杂度：O(n × k)
空间复杂度：O()
单调队列 Monotonic Queue
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = collections.deque() # 和单调栈一样，队列中保存的是indices
res = []
for i, cur in enumerate(nums):
while q and nums[q[-1]] <= cur: # 因为迭代前面已有保证，这次把queue右边比自己小的没用了，可以pop出去
q.pop()
q.append(i)
# 特别之处在这里: 超过滑动滑口的部分pop出去, 在已有迭代基础上 每次pop一个即可
if q[0] == i - k:
q.popleft()
# 如果窗口已经达到k的大小，记录最大值. 不够k的window不算
if i >= k - 1:
res.append(nums[q[0]])
return res
class MyQueue(object):
def __init__(self):
self.q = collections.deque()
def pop(self, value):
# 保证队列里是单调的，非空且等于出口时弹出
# 这里是if 和 q[0]，我自己写的while 和 q[-1], 这里多写大于等于更是问题了
if self.q and value == self.q[0]:
self.q.popleft()
def push(self, value):
# 非空，push的值大于最小值时，一直弹出
# 该value位置之前比他小的肯定是没用的了, 注意是>。等于的先留着？
while self.q and value > self.q[-1]:
self.q.pop()
self.q.append(value)
@property
def front(self): # 当前队列最大值, 第0
return self.q[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = MyQueue()
res = []
for i in range(k):
q.push(nums[i])
res.append(q.front)
for i in range(k, len(nums)):
q.pop(nums[i - k]) # 关键思路，所以单调队列的pop是带元素的
q.push(nums[i])
res.append(q.front)
return res