单调队列（Monotonic Queue）
1. 前提条件

单调队列主要解决：滑动窗口最值问题

典型题：

239. 滑动窗口最大值（经典）

例如：给一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

nums = [1,3,-1,-3,5,3,6,7]

k = 3

窗口：

[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

……

输出：3 3 5 5 6 7

2. 为什么不能暴力？

暴力：

for(i)
{
    遍历窗口

    找最大
}

复杂度：n*k

3. 核心思想

队列里面保存当前窗口

可能成为最大值的元素

例如：

窗口：

1

3

来了：2

那么：3比2大

以后：2

永远不可能成为最大值

因为：3

一直挡在它前面。

所以：2

不用删除。

但是如果：

来了：5

那么：

5>2

5>3

5>1

说明：

1

2

3

以后都不可能成为最大值。

全部删掉。

所以叫单调队列。

4. 为什么叫单调？

例如维护窗口最大值。

队列从队头到队尾

单调递减。

例如：

8

6

5

2

队头一定最大。

所以答案永远：

queue[front]

5. 队列里面放什么？

和单调栈一样。

放下标不是值。

因为窗口会移动。

必须知道哪个元素已经出了窗口。

例如：

窗口：

[1 3 -1]

对应：

0

1

2

下一次：

窗口：

[3 -1 -3]

下标：

0：

已经离开。

必须删除。

所以必须存下标。

6. 固定模板
for(int i=0;i<n;i++)
{
    //① 删除已经离开窗口
    while(front<=rear &&
          queue[front]<=i-k)
    {
        front++;
    }

    //② 保持单调递减
    while(front<=rear &&
          nums[queue[rear]]<=nums[i])
    {
        rear--;
    }

    //③ 当前元素入队
    queue[++rear]=i;

    //④ 窗口形成
    if(i>=k-1)
    {
        ans[index++]=nums[queue[front]];
    }
}


就是这个模板。

7. C代码（239）
int* maxSlidingWindow(int* nums,
                      int numsSize,
                      int k,
                      int* returnSize)
{
    int queue[100001];

    int front=0;

    int rear=-1;

    int* ans=
        malloc((numsSize-k+1)*sizeof(int));
//窗口个数
    int index=0;

    for(int i=0;i<numsSize;i++)
    {// 删除已经滑出当前窗口的下标（也就是超出窗口范围的元素删除和已经再无可能成为最大值的元素删除）
        while(front<=rear &&
              queue[front]<=i-k)
        {
            front++;
        }
// 删除队尾中比当前 nums[i] 小或相等的元素
// 因为它们以后不可能成为最大值
        while(front<=rear &&
              nums[queue[rear]]<=nums[i])
        {
            rear--;
        }
// 当前下标 i 入队，作为候选最大值
//queue数组不删元素，只是有效值的区间变了
        queue[++rear]=i;
// 从第一个完整窗口开始，每一轮输出队头对应的值
        if(i>=k-1)
        {
            ans[index++]=
                nums[queue[front]];
        }
    }

    *returnSize=index;

    return ans;
}
8. 举例

数组：

1 3 -1 -3 5 3 6 7

窗口：

k=3
i=0

来了：

1

队列：

空。

入队：

1

对应：

下标：

0
i=1

来了：

3

比较：

3>1

说明：

1

以后永远：

不会成为最大值。

弹：1

然后3入队。

队列：

3

对应：
1

i=2来了：-1

比较：-1>3？

不是。

直接入队。

得到：

3

-1

窗口：形成最大队头

=

3

输出：

3
i=3

窗口：

右移。

现在：

窗口：

3

-1

-3

先：

检查：

有没有：

过期。

队头：

1

对应：

3

没有：

过期。

然后：

-3

入队。

得到：

3

-1

-3

最大：

还是：

3
i=4

来了：

5

首先：

窗口：

移动。

队头：

3

已经：

过期。

删。

然后：

比较：

5>-3

弹

5>-1

弹

5>3

弹

全部：

弹掉。

队列：

空。

最后：

5：

入队。

得到：

5

以后：

最大：

一直：

5。

9. 为什么也是 while？

例如：队列：

8

6

4

2

来了10

必须一直删。

10>2删
10>4删
10>6删
10>8删

如果if只能删一个。

所以必须while。

10. 时间复杂度

很多人：

觉得：

while

是不是

O(n²)?

其实：

不是。

因为：

每个元素：

最多：

入队一次

出队一次

所以：总共2n

复杂度：O(n)
11. 单调栈           单调队列
单调栈	            单调队列
最近更大/更小	    滑动窗口最值
LIFO（后进先出）	FIFO（先进先出）
维护单调性	        维护单调性
保存下标	        保存下标
每个元素进出一次	每个元素进出一次
O(n)	O(n)

12. 易错点
① 队列存下标，不存值。

② 先删过期元素，再维护单调性。

③ while，不是if。

④ 队头永远是当前窗口最大值。

⑤ i>=k-1 才开始输出答案。
13. 总结
单调队列

作用：滑动窗口最大/最小值

--------------------------------

维护：

单调递减队列

队头：

永远最大

--------------------------------

步骤：

① 删除窗口外元素

② 删除队尾较小元素

③ 当前元素入队

④ 输出队头

--------------------------------

复杂度：

O(n)

因为：

每个元素

最多：

进一次

出一次。
单调栈和单调队列的最终区别（一定要记住）



单调栈：

"我不知道右边什么时候会出现答案，所以先压栈等待。"

↓

用于：最近更大、最近更小。

--------------------------------

单调队列：

"窗口一直在移动，我要维护当前窗口的最优元素。"

↓

用于：滑动窗口最大值、最小值。