单调队列算法模板如何应用于实际问题？

本文共计1500个文字，预计阅读时间需要6分钟。

文章和代码已归档至以下链接：- [Github 仓库：https://github.com/timerring/algorithms-notes]- 或 [AIShareLab 回复]- 算法笔记也可获取。序列算法模板：/ / 表示头部，tt 表示尾部，int q[N];hh=0, tt=-1;/ / 向队列进队

文章和代码已经归档至或者回复 算法笔记 也可获取。

队列算法模板

// hh 表示队头，tt表示队尾 int q[N], hh = 0, tt = -1; // 向队尾插入一个数 q[ ++ tt] = x; // 从队头弹出一个数 hh ++ ; // 队头的值 q[hh]; // 对尾的值 q[tt]; // 判断队列是否为空 /* if(hh <= tt) not empty else empty */ if (hh <= tt) { }

例题：滑动窗口

单调队列的应用：求滑动窗口中的最大值和最小值

第一步把新元素插入队尾，第二步把滑出去的元素从队首弹出来。

给定一个大小为 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。