单调队列
- 什么是单调队列？
- 满足两个性质：
- 从队头到队尾，元素在我们所关注的指标下是递减的（严格递减，而不是非递增。比如查询如果每次问的是窗口内的最小值，那么队列中元素从左至右就应该递增，如果每次问的是窗口内的最大值，则应该递减，依此类推。这是为了保证每次查询只需要取队头元素。
- 从队头到队尾，元素对应的时刻（此题中是该元素在数列a中的下标）是递增的，但不要求连续，这是为了保证最左面的元素总是最先过期，且每当有新元素来临的时候一定是插入队尾。
- 支持两种操作：
- 插入：
- 首先要保证新的元素在后面（性质2），其次要求严格递减（性质1）
- 所以找到第一个大于插入数的数，将其及之后删去，然后插入
- 为什么删？因为所有被删除的元素都比新元素要小，且比新元素旧，所以可以放心删除
- 查询：
- 所有过期元素都在队头，所以删除后所得头元素便是查询的答案
- 单调队列有什么作用？
- 为什么要用它？跟普通的 int max 相比有什么区别？
- 最大连续子序列，为什么能用单调序列做？
参考链接
单调队列_innocence的博客-CSDN博客
C++ list（STL list）容器完全攻略（超级详细） (biancheng.net)