考试题解
考试题解链接
1. STACK 栈
特点：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. QUEUE 队列
特点：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. DEQUE 双端队列
单调队列最常用：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. PRIORITY_QUEUE 优先队列
默认是大根堆：
小根堆：
此时：
最简口诀：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PTA-LITTLE BIRD
琪露诺
暴力DP
单调队列DP优化
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
单调队列笔记
1. 作用
求长度为 kkk 的滑动窗口中的最小值或最大值。
当前窗口：
[i−k+1,i][i-k+1,i][i−k+1,i]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 核心思想
deque 中存下标。
求最小值时，维护：
所以：
就是当前窗口最小值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 三步操作
窗口形成后：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 为什么队尾可以删除
假设队尾是 5，当前来了 3：
3：
* 比 5 小；
* 比 5 更晚离开窗口。
所以以后 5 不可能成为最小值，可以直接删除。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 完整代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 求最大值
最小值：
最大值改成：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 复杂度
每个元素最多入队、出队一次。
时间复杂度：
O(n)O(n)O(n)
空间复杂度：
O(k)O(k)O(k)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 口诀
最小值：维护单调递增。
最大值：维护单调递减。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
单调栈学习笔记
一、什么是单调栈
单调栈本质还是一个普通的 stack，只不过我们通过不断弹栈，使栈中的元素保持单调。
常见两种：
单调栈最常解决的问题：
* 左边第一个比我大的元素
* 左边第一个比我小的元素
* 右边第一个比我大的元素
* 右边第一个比我小的元素
* 柱状图最大矩形
* 统计某个数作为区间最大值、最小值的贡献
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、核心理解
不要死记“维护单调性”。
可以理解成：
> 栈里面存的都是“还没有找到答案的人”。
例如要求：
> 右边第一个比自己大的元素。
当前来了一个新元素 a[i]。
如果：
说明当前元素就是栈顶元素一直等待的答案。
所以：
继续看新的栈顶。
直到栈顶不比当前元素小，再把当前元素入栈等待自己的答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、右边第一个比我大的元素
例如：
答案：
所以：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
模拟过程
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、为什么栈是单调的
还是求：
> 右边第一个比我大的元素。
代码：
所有比当前 a[i] 小的元素都会被弹掉。
所以最后留下来的栈顶一定满足：
然后再把 i 放进去。
因此栈中的值自然形成：
也就是一个单调递减栈。
所以：
> 不是为了单调而单调，而是“已经找到答案的人被弹掉”，剩下的人自然形成了单调性。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、四种经典模板
1. 右边第一个更大
从左往右扫：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 右边第一个更小
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 左边第一个更大
当前元素把比自己小的全部弹掉。
弹完以后，栈顶就是左边第一个更大的元素。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 左边第一个更小
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、怎么判断扫描方向
可以简单记：
求右边的答案
通常：
当前元素帮助前面的元素得到答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
求左边的答案
通常：
先弹掉不合法元素，然后直接看：
就是左边最近满足条件的位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、为什么是 O(N)O(N)O(N)
虽然代码里面有：
看起来像 O(n2)O(n^2)O(n2)。
但是每一个元素：
例如：
元素 1 被弹掉以后，就永远不会重新进入栈。
所以所有 while 加起来最多弹 nnn 次。
因此总时间复杂度：
O(n)O(n)O(n)
空间复杂度：
O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、经典应用：发射站
如果一个发射站的能量，会被左右两边最近且比它高的发射站接收。
当前处理第 i 个位置：
被弹出的元素：
> 当前 i 就是它右边第一个比它高的位置。
弹完以后：
此时栈顶：
> 就是 i 左边第一个比它高的位置。
模板：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、区间最大值贡献
很多题会求：
> 所有子区间最大值之和。
对于每个 a[i]，找到：
那么以 a[i] 作为最大值的区间数量：
(i−L)×(R−i)(i-L)\times(R-i)(i−L)×(R−i)
贡献就是：
最小值同理。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、相等元素的注意事项
如果数组中可能有相等元素：
左右两边都使用严格比较，可能导致同一个区间被重复统计。
做贡献题时通常需要：
例如最大值：
最小值：
这样可以保证每个区间只归属于一个位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、单调栈核心口诀
再记一句：
> 栈里留下的是还没有找到答案的人。
这就是单调栈最核心的思想。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十二、常见错误
1. 栈里建议存下标
推荐：
存位置，比较时：
这样既能得到值，也能得到下标。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 注意严格和非严格
在有重复元素时区别很大。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 不存在时答案通常为 000
全局数组默认：
所以没有找到答案的元素可以不用额外处理。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. WHILE 不是 IF
必须：
因为一个当前元素可能同时解决很多前面的元素。
例如：
当前 6 可以一次弹：
所以一定是 while。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结
单调栈主要解决：
> 某个元素左边或右边，第一个比它大 / 小的位置。
最重要的理解：
当前元素出现后：
每个元素最多入栈、出栈一次，因此时间复杂度为 O(n)O(n)O(n)。
平衡数组
单调栈
发射站
