单调队列&单调栈
感觉我有限的智力难以理解，因此写下来研究一下（
单调队列
顾名思义，单调队列就是一个队列内容有单调性的队列（
我们可以用单调队列来维护一列数据中，某长度段连续的子区间中的最大/最小值
例如，给定一串数字，求其每个长度为m的连续子区间的最小值
相较于ST表，线段树等数据结构，单调队列均摊复杂度O（n），会快很多
以下以一个递减的单调队列为例，简单描述一下如何构造单调队列：
在区间往后移动了一位后，我们假定新出现的数字为A
- 单调队列的队首是以前加入的，那么它可能不在新的区间中，进行判断是否需要将其删除
- 如果A比队尾的数字小，没有破坏单调性，我们可以直接把A加入队尾
- 如果A比队尾的数字大，因为A是新加入的数字，它可能在未来的某个区间中成为区间最大值，而在队中，且比A小的数字一定存在于包含A的区间中，且没有A大，所以
没用删掉完事
这样我们就构造出了一个单调队列
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include<vector>
#include<iomanip>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n, k;
struct node
{
int id, val;
node(int x=0, int y=0) { id = x, val = y; };
}que[1000000+5],que2[1000000+5];
int dataa[2000000];
int ans1[1000000+5],ans2[1000000+5];
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++)scanf("%d", &dataa[i]);
int l1 = 0, r1 = -1, l2 = 0 ,r2=-1; //初始化队头队尾指针
for (int i = 0; i < n; i++) {
node now = node(i, dataa[i]);
//单调减队列
while (l1 <= r1 && que[l1].id < now.id - k + 1)l1++; //去头
while (l1 <= r1 && que[r1].val < now.val)r1--; //去尾
que[++r1] = now;
ans1[i] = que[l1].val; //ans[i]储存以i为结尾的区间内的极值
//单调增队列
while (l2 <= r2 && que2[l2].id < now.id - k + 1)l2++;
while (l2 <= r2 && que2[r2].val > now.val)r2--;
que2[++r2] = now;
ans2[i] = que2[l2].val;
}
for (int i = k - 1; i < n; i++)cout << ans2[i] << ' ';
cout << "
";
for (int i = k - 1; i < n; i++)cout << ans1[i] << ' ';
}
单调栈
单调栈就是栈内元素出栈序列单调有序的栈
没了
要实现单调栈，我们只需要进行一下操作（以下操作是单调递增栈，即出栈序列递增）
- 我们要想令一个值A入栈时，首先检查栈顶元素是否大于A
- 栈顶元素大于等于A，A可以直接入栈
- 栈顶元素小于A，一直将栈顶元素出栈，直到栈顶元素大于A，随后A入栈
PS.我们构造单调栈时，栈内储存的是元素的下标，而不是元素的值
那么这玩意有啥用呢（
使用单调栈，我们可以解决诸如寻找数列中某个数之前/后第一个大于/小于它的数的问题
正确性：
我们以寻找某个数前，第一个大于他的数为例
构造一个单调递增的栈，设当前数为A，此时
- 栈顶元素一定是在A之前就出现的数
- 栈顶元素一定是A的前一个数，如果A比栈顶元素小，那么A之前第一个大于它的数肯定是栈顶
- 如果A大于栈顶元素，栈顶元素出栈，现在栈顶就是前栈顶之前第一个大于它的数，以此类推，当不能再出栈后，栈顶即为正解
以下代码：洛谷：P5788 【模板】单调栈
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include<vector>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#define lc(i) (2*i+1)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n, k;
stack<long long>sk;
ll dataa[3000000 + 5];
ll ans[3000000 + 5];
int main() {
cin >> n;
for (int i = 0; i < n; i++)scanf("%d",&dataa[i]);
for (int i = n - 1; i >= 0; i--) {
while (!sk.empty() && dataa[sk.top()] <= dataa[i])sk.pop();
if (sk.empty())ans[i] = -1;
else ans[i] = sk. top();
sk.push(i);
}
for (int i = 0; i < n; i++)cout << ans[i]+1 << ' ';
}