详解单调队列算法

前言 嘿！彩蛋！感觉有帮助就三连呗！

如果你对这篇文章可感兴趣，可以点击「【访客必读 – 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

在上一篇文章中，我们介绍了「单调栈」这一最常考察的线性数据结构。而今天我们将继续沿着这个思路，介绍另一个与其 “齐名” 的线性数据结构，即「单调队列」。

「单调队列」在「数据结构」题中的分布较为广泛，且常被当作优化「动态规划」的一种重要手段，因此该算法在面试中考察的频率较高，属于必知必会的知识点。

队列

首先我们来回忆一下「队列」。「队列」是一种「先进先出」的线性数据结构，其中元素只能从队尾进，从队首出。

如下图所示，3 1 4 5 2 7 依次入队又依次出队，其结果满足「先进先出」的要求。另外，有标记的位置分别代表队首与队尾，其中左边为队首。

单调队列

回忆完「队列」后，我们开始「单调队列」的讲解。

什么是「单调队列」？顾名思义，「单调队列」就是队列内元素满足单调性的队列结构。且为了满足队列内元素的单调性，队尾也可弹出元素。此处的单调性分为单调递增与单调递减，为了便于描述，接下来以「单调递增队列」为例进行讲解。