单调队列-滑动窗口最大值

题目描述

给定一个长度为n的数组和一个大小为m的滑动窗口（0＜m≤n），请找出所有滑动窗口里的最大值。

例如，数组{2,6,4,9,8,5,5,2}，滑动窗口的大小为3，那么一共存在6个滑动窗口，它们的最大值分别为6,9,9,9,8,5。

代码详解

展开查看

a = [0,2,6,4,9,8,5,5,2]
m = 3

for i in range(m, len(a)):
    mx = a[i]
    for j in range(i-m+1, i+1):
        mx = max(mx, a[j])
    print(mx)

展开查看

#单调队列
a = [0,2,6,4,9,8,5,5,2]
q = [0,1,2,3,4,5,6,7,8]
m = 3

h = 0
t = -1
for i in range(1, len(a)):
    #q[h]不在窗口[i-m+1]内，队头出队
    if h<=t and q[h]<i-m+1:
        h += 1
    #当前值>=队尾值，队尾出队
    while h<=t and a[i]>=a[q[t]]:
        t -= 1
    #下标入队，便于队头出队
    t+=1
    q[t] = i
    #使用队头最大值
    if i > m - 1: #满3个时才输出
        print(a[q[h]])

运行结果

展开查看