day03 单调栈、单调队列

单调栈

定义：内部元素满足单调性的栈。

用途：线性时间内处理出数组中每一个元素 左边/右边 第一个 大于/小于 此元素 的位置。

• 单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小，每当遇到比栈顶大的元素就弹栈
• 单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大，每当遇到比栈顶小的元素就弹栈

特性：关联容器与线性结构有着根本性的不同，线性结构的元素是按照在容器中的位置来顺序保存和访问的，而关联容器的元素是按关键元素来保存和访问的。关联容器支持高效的关键字查找与访问。两个主要的关联容器类型是map与set。

模板题目思路

模拟一遍单调栈的运行过程，这里的单调栈是单调递增栈。

现在有 6 个数 5,2,3,4,1,6。

要明白，存放的是下标。然后，直接把元素放在栈顶，会破坏它的单调性。所以需要吐出栈顶的元素，使得当前的元素再加进去不会破坏它的单调性。

• 当前栈内没有元素，将 5 加入。现在栈内元素应该是 1。
• 当前元素为 2，我们发现加入之后不能单调，于是吐出 5，加入 2。当前栈内元素为 2。
• 接下来是 3,4。我们发现加入不会破坏单调性，于是直接加入，栈内元素 2,3,4。
• 遇到 1，只能吐出栈内所有元素，加入 1。
• 最后加入 6。整个算法流程完成。

单调队列

特性

1. 队列中的元素其对应在原来的序列中的顺序必须是单调递增的。
2. 队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)

特点

单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队，也可以从队尾出队。

模板题目思路

以样例来计算，设以最小的为标准。

8 3
1 3 -1 -3 5 3 6 7

下文中用q来表示单调队列，p来表示其所对应的在原列表里的序号。

1. 由于此时队中没有一个元素，直接令1进队。此时，q={1},p={1}。
2. 现在3面临着抉择。下面基于这样一个思想:假如把3放进去，如果后面2个数都比它大，那么3在其有生之年就有可能成为最小的。此时，q={1,3},p={1,2}
3. 下面出现了-1。队尾元素3比-1大，那么意味着只要-1进队，那么3在其有生之年必定成为不了最小值，原因很明显:因为当下面3被框起来，那么-1也一定被框起来，所以3永远不能当最小值。所以，3从队尾出队。同理，1从队尾出队。最后-1进队，此时q={-1},p={3}
4. 出现-3，同上面分析，-1>-3，-1从队尾出队,-3从队尾进队。q={-3}，p={4}。
5. 出现5，因为5>-3，同第二条分析，5在有生之年还是有希望的，所以5进队。此时，q={-3,5},p={4,5}
6. 出现3。3先与队尾的5比较，3<5，按照第3条的分析，5从队尾出队。3再与-3比较，同第二条分析，3进队。此时，q={-3,3},p={4,6}
7. 出现6。6与3比较，因为3<6，所以3不必出队。由于3以前元素都＜3，所以不必再比较，6进队。因为-3此时已经在滑动窗口之外，所以-3从队首出队。此时，q={3,6},p={6,7}
8. 出现7。队尾元素6小于7，7进队。此时，q={3,6,7},p={6,7,8}。

那么，我们对单调队列的基本操作已经分析完毕。因为单调队列中元素大小单调递*(增/减/自定义比较)，因此，队首元素必定是最值。按题意输出即可。

家庭作业

必做：丑数、比赛：洛谷语言入门月赛（2022 年 9 月）复刻，4道

提高：小码君的数字集合，上述比赛AK

//丑数一题中思维过程
#include <iostream>
#include <deque>
using namespace std;
int main(){
	//输入数据
	//准备三个队列，分别存放每个2的倍数、3的倍数、5的倍数
	//各自预先储存一个1进去
	//循环n次，表示正在计算第n个丑数
		//找到三个队列中，队首元素 最小的一个
			//if 取出来的数 是第一个队列队首元素  出队
			//if 取出来的数 是第二个队列队首元素  出队
			//if 取出来的数 是第三个队列队首元素  出队
		//将取出来的数的2倍 放入第一个队列
		//将取出来的数的3倍 放入第二个队列
		//将取出来的数的5倍 放入第三个队列
	//输出第n次循环的三个队列中最小的队首元素
	return 0;	
}