问题背景可参考
这里主要谈一谈我对单调队列方法的理解；我们举一个例子，给定大小为9的数组 [ 1 , 3 , − 1 , − 3 , 5 , 3 , 6 , 7 ] [1,3,-1,-3,5,3,6,7] [1,3,−1,−3,5,3,6,7]，滑动窗口大小为3.
我们这里维护一个队列 Q Q Q（这里就不谈它是单调队列 了，我们现在重点要理解的就是它为什么会是单调队列，所以就先把它当作一个普通的队列），我们假设对 Q Q Q可以执行 p o p pop pop和 p u s h push push两种操作，为便于表达队列的方向，我们记空的队列为 Q [ h e a d , t a i l ] Q[head,tail] Q[head,tail]，比如对一个空的队列进行 Q . p u s h ( 2 ) Q.push(2) Q.push(2)操作可以得到 Q [ h e a d , 2 , t a i l ] Q[head,2,tail] Q[head,2,tail]，再进行 Q . p u s h ( 3 ) Q.push(3) Q.push(3)操作可以得到 Q [ h e a d , 2 , 3 , t a i l ] Q[head,2,3,tail] Q[head,2,3,tail]，执行 Q . p o p ( ) Q.pop() Q.pop()操作可以得到 Q [ h e a d , 3 , t a i l ] Q[head,3,tail] Q[head,3,tail]
现在假设我们希望知道滑动窗口从左滑到右过程中每时每刻的最大值，并且每时每刻去查询最大值的时间复杂度都是 O ( 1 ) O(1) O(1)（如果每次都去滑动窗口中遍历一遍，则时间复杂度是 O ( k ) O(k) O(k)， k k k是滑动窗口的大小），这里使用的方法就是用队列 Q Q Q去维护一些信息，使得滑动窗口移动的时候能在 O ( 1 ) O(1) O(1)时间内完成这些信息的更新，假设我们希望 Q Q Q的队首元素就是当前滑动窗口的最大值
这是最初的情况
[
[
]
1
,
3
,
−
1
,
−
3
,
5
,
3
,
6
,
7
]
[[]1,3,-1,-3,5,3,6,7]
[[]1,3,−1,−3,5,3,6,7]
Q
[
h
e
a
d
,
t
a
i
l
]
Q[head,tail]
Q[head,tail]
现在滑动窗口纳入第一个元素
[
[
1
]
,
3
,
−
1
,
−
3
,
5
,
3
,
6
,
7
]
[[1],3,-1,-3,5,3,6,7]
[[1],3,−1,−3,5,3,6,7]
Q
[
h
e
a
d
,
1
,
t
a
i
l
]
Q[head,1,tail]
Q[head,1,tail]
现在滑动窗口要纳入第二个元素，那么问题来了，现在该如何操作？这里的关键就是可以把数组中每个元素中带上时效性或寿命去理解，这里滑动窗口的大小是3，因此每个元素被涵盖在滑动窗口中的最大时间就是3，我们可以这样认为当滑动窗口的右边第一次覆盖到一个元素的时候，这个元素就“出生了”，我们可以给它赋一个年龄0岁，接着滑动窗口每往右移一格，这个元素就多一岁，当滑动窗口的左边移出这个元素时，这个元素就“死亡了”，假设我们使用
−
1
-1
−1表示一个元素未“出生”或已经“死亡”，则可以把当前数组写为这样，括号中就是这个元素当前的寿命情况：
[
[
1
(
0
)
]
,
3
(
−
1
)
,
−
1
(
−
1
)
,
−
3
(
−
1
)
,
5
(
−
1
)
,
3
(
−
1
)
,
6
(
−
1
)
,
7
(
−
1
)
]
[[1(0)],3(-1),-1(-1),-3(-1),5(-1),3(-1),6(-1),7(-1)]
[[1(0)],3(−1),−1(−1),−3(−1),5(−1),3(−1),6(−1),7(−1)]
Q
[
h
e
a
d
,
1
(
0
)
,
t
a
i
l
]
Q[head,1(0),tail]
Q[head,1(0),tail]
当滑动窗口右边移动到下一格时，所有元素的寿命情况更新了：
[
[
1
(
1
)
,
3
(
0
)
]
,
−
1
(
−
1
)
,
−
3
(
−
1
)
,
5
(
−
1
)
,
3
(
−
1
)
,
6
(
−
1
)
,
7
(
−
1
)
]
[[1(1),3(0)],-1(-1),-3(-1),5(-1),3(-1),6(-1),7(-1)]
[[1(1),3(0)],−1(−1),−3(−1),5(−1),3(−1),6(−1),7(−1)]
Q
[
h
e
a
d
,
1
(
1
)
,
t
a
i
l
]
Q[head,1(1),tail]
Q[head,1(1),tail]
那么我们现在应该怎样处理新“出生”的元素3呢？我们需要把它插入到元素1的前面吗（这样才能保证时刻队首元素是当前滑动窗口的最大值）。其实不用，因为1(1)比3(0)要老，换句话说它会比3早死，而由于1比3小，所以在剩下1的余生中，它都没用了，当我们查询最大值的时候，只会去查询它的晚辈了（可能之后还有更大的晚辈出生，不过不管怎么说，这个1已经没用了），既然没用了，我们就可以把它丢弃了，当它死了都行
[
[
1
(
1
)
,
3
(
0
)
]
,
−
1
(
−
1
)
,
−
3
(
−
1
)
,
5
(
−
1
)
,
3
(
−
1
)
,
6
(
−
1
)
,
7
(
−
1
)
]
[[1(1),3(0)],-1(-1),-3(-1),5(-1),3(-1),6(-1),7(-1)]
[[1(1),3(0)],−1(−1),−3(−1),5(−1),3(−1),6(−1),7(−1)]
Q
[
h
e
a
d
,
3
(
0
)
,
t
a
i
l
]
Q[head,3(0),tail]
Q[head,3(0),tail]
接着来，又有一位晚辈出生了
[
[
1
(
2
)
,
3
(
1
)
,
−
1
(
0
)
]
,
−
3
(
−
1
)
,
5
(
−
1
)
,
3
(
−
1
)
,
6
(
−
1
)
,
7
(
−
1
)
]
[[1(2),3(1),-1(0)],-3(-1),5(-1),3(-1),6(-1),7(-1)]
[[1(2),3(1),−1(0)],−3(−1),5(−1),3(−1),6(−1),7(−1)]
Q
[
h
e
a
d
,
3
(
1
)
,
t
a
i
l
]
Q[head,3(1),tail]
Q[head,3(1),tail]
这回有一点不同，这个晚辈不是值最大的，那么我们是否可以丢弃这个晚辈当它没出生呢？这是不行的，因为这个-1会比当前的最大值3活的更久，虽然在3存活的期间，它永远都是最大的，但是等这个3死了，后面的事情还不好说呢
[
[
1
(
2
)
,
3
(
1
)
,
−
1
(
0
)
]
,
−
3
(
−
1
)
,
5
(
−
1
)
,
3
(
−
1
)
,
6
(
−
1
)
,
7
(
−
1
)
]
[[1(2),3(1),-1(0)],-3(-1),5(-1),3(-1),6(-1),7(-1)]
[[1(2),3(1),−1(0)],−3(−1),5(−1),3(−1),6(−1),7(−1)]
Q
[
h
e
a
d
,
3
(
1
)
,
−
1
(
0
)
,
t
a
i
l
]
Q[head,3(1),-1(0),tail]
Q[head,3(1),−1(0),tail]
现在滑动窗口已经最大化了，要开始同时向右移了，最早出生的1迎来了死亡，不过由于它很早就已经没用了，我们很早就当它已经死了，所以不用管它，对于新降生的-3，同样要把它纳入队列
[
1
(
−
1
)
,
[
3
(
2
)
,
−
1
(
1
)
,
−
3
(
0
)
]
,
5
(
−
1
)
,
3
(
−
1
)
,
6
(
−
1
)
,
7
(
−
1
)
]
[1(-1),[3(2),-1(1),-3(0)],5(-1),3(-1),6(-1),7(-1)]
[1(−1),[3(2),−1(1),−3(0)],5(−1),3(−1),6(−1),7(−1)]
Q
[
h
e
a
d
,
3
(
2
)
,
−
1
(
1
)
,
−
3
(
0
)
,
t
a
i
l
]
Q[head,3(2),-1(1),-3(0),tail]
Q[head,3(2),−1(1),−3(0),tail]
滑动窗口再向右移动，这回发生了不得了的事，顶梁柱（当前值最大的元素）死了，我们要把它移出队列，这里可以看到它的晚辈刚好就仍然是当前滑动窗口中最大的
[
1
(
−
1
)
,
3
(
−
1
)
,
[
−
1
(
2
)
,
−
3
(
1
)
]
,
5
(
−
1
)
,
3
(
−
1
)
,
6
(
−
1
)
,
7
(
−
1
)
]
[1(-1),3(-1),[-1(2),-3(1)],5(-1),3(-1),6(-1),7(-1)]
[1(−1),3(−1),[−1(2),−3(1)],5(−1),3(−1),6(−1),7(−1)]
Q
[
h
e
a
d
,
−
1
(
2
)
,
−
3
(
1
)
,
t
a
i
l
]
Q[head,-1(2),-3(1),tail]
Q[head,−1(2),−3(1),tail]