单调队列模拟-野牛程序员教少儿编程

单调队列模拟

目标：用单调递减队列求滑动窗口最大值。

问题：

数组：[4, 2, 12, 3, 8, 7]

窗口大小：3

模拟过程开始！

初始状态：

队列为空，窗口准备从左往右滑。

第一步：i = 0，数值 = 4

队列空，直接放进去。

队列：[4]

第二步：i = 1，数值 = 2

2 比队尾 4 小，不能干掉它，老老实实排后面。

队列：[4, 2]

第三步：i = 2，数值 = 12

来了个大哥！

比队尾 2 大 踢走

再比前面 4 大 继续踢走

队列空了，大哥自己进来

队列：[12]

滑动窗口[4,2,12]最大值是：12

第四步：i = 3，数值 = 3

3 比 12 小，排队

队列：[12, 3]

窗口[2,12,3]最大值还是：12

第五步：i = 4，数值 = 8

8 > 3 踢掉 3

8 < 12 进队

队列：[12, 8]

窗口[12,3,8]最大值是：12

第六步：i = 5，数值 = 7

7 < 8，直接进队

队列：[12, 8, 7]

但 12 对应的是 i = 2，已经滑出窗口（窗口是 i=3~5）

踢掉 12

队列剩下：[8, 7]

窗口[3,8,7]最大值是：8

最终输出的最大值列表是：

[12, 12, 12, 8]

可视化图（队列内容）：

野牛程序员教少儿编程与信息学奥赛

宜宾市野牛网络科技有限公司专业微信小程序开发、网站建设、软件开发等