单调队列
时间复杂度: $O(n)$
对于单调队列求最小值问题,如果后进入队列的数比原来队列的数字还要小,那就踢掉队列末尾的数字
(新人比你年轻还比你强,那你还有存在的必要吗?)
最大值问题同理
一般步骤:以求单调队列最小值为例
1. 如果队列非空且新进入窗口的元素小于队列末尾的元素,则将队尾元素踢出
2. 将该元素入队
3. 如果队头滑出了窗口,则把队头元素踢出
4. 每一轮的队头元素就是最小值
deque
python双端队列:deque
头文件:import collections
初始化队列:dq = collections.deque()
队尾插入元素:dq.append(i)
踢出队尾元素:dq.pop()
踢出队头元素:dq.popleft()
python代码
# from collections import deque
# res = deque([])
import collections
res = collections.deque()
n, k = map(int, input().split())
ls = list(map(int, input().split()))
for i in range(n):
while len(res) != 0 and res[-1] > ls[i]:# 新进入窗口的值小于队尾元素,则队尾出队列
res.pop()
res.append(ls[i])# 将新进入的元素入队
if i - k >= 0 and res[0] == ls[i - k]: # 若队头是否滑出了窗口,队头出队 ,前一个判断条件保证此时窗口形成了,否则总共两个数怎么形成窗口
res.popleft()
if i - k + 1 >= 0:# 当窗口形成,输出队头对应的值
print(res[0], end = " ")
# res = deque([])
res = collections.deque()
print()
for i in range(n):
while len(res) != 0 and res[-1] < ls[i]:
res.pop()
res.append(ls[i])
if i - k >= 0 and res[0] == ls[i - k]:
res.popleft()
if i >= k - 1:
print(res[0], end = " ")