单调队列应用介绍
单调队列应用介绍
- 定义
- 应用场景
- 实现模板
- 具体示例
-
- 滑动窗口最大值
-
- 问题描述
- 问题分析
- 代码实现
- 带限制的子序列和
-
- 问题描述
- 问题分析
- 代码实现
- 跳跃游戏
-
- 问题描述
- 问题分析
- 代码实现
定义
队列(Queue)是另一种操作受限的线性表，只允许元素从队列的一端进，另一端出，具有先进先出(FIFO)的特性。但**单调队列(Monotonic Queue)**是一种特殊的队列，它首先是一个双端队列（可在队头/队尾进行读写），其次队列内部的元素单调递增/递减。
单调队列具有以下特性：
- 当前最优解在队头
- 插入元素都是从队尾插入
- 会剔除队尾不符合单调性的元素(类似栈的出栈动作)
- 会弹出队头不满足区间限制的元素（单调队列解决的问题一般都带有区间限制）
因此，可以把 单调队列看作是 滑动窗口 和 单调栈 的组合体。
应用场景
-
解决滑动窗口的最值问题
比如滑动窗口内的最大值问题
-
适用于最优化DP(动态规划)算法中动态规划转移，对应的动态转移方程类似 f ( i ) = max l < = j < = r ( f ( j ) + b ( j ) + a ( i ) ) = max l < = j < = r ( f ( j ) + b ( j ) ) + a ( i ) f(i) = \max_{l<=j<=r}(f(j) + b(j) + a(i)) = \max_{l<=j<=r}(f(j) + b(j)) + a(i) f(i)=l<=j<=rmax(f(j)+b(j)+a(i))=l<=j<=rmax(f(j)+b(j))+a(i)，其中 max l < = j < = r ( f ( j ) + b ( j ) ) \max_{l<=j<=r}(f(j) + b(j)) l<=j<=rmax(f(j)+b(j