单调双端队列

定义

具有单调性，且仅允许双端操作的线性表

• 单调栈
• 单调队列

二者核心一致，区别在于是否需要访问队首

核心

通过单调性，筛选普通线性表的有效部分

例：筛选递增部分
1 3 2 4 7 5 9
1 3     7   9

注：一般存储数组下标，方便去重和访问原数组

队内元素可理解为“候选元素”

单调栈

仅允许队尾操作的单调双端队列

应用

用于记录单点特性（全局信息有效）

	入栈时结算	出栈时结算
递增栈	上一个更小元素	下一个更小元素
递减栈	上一个更大元素	下一个更大元素
栈内意义	存储可利用元素	存储待处理元素

入栈、出栈时分别结算元素，可一次遍历求出左侧、右侧目标值

单调队列

允许队首和队尾操作的单调双端队列

应用

用于记录区间特性（局部信息有效）

	递增队列	递减队列
信息	单侧最小值	单侧最大值
获取方式	取队首

常配合滑动窗口，维护区间