单调队列及其相关题解

单调队列：

1.单调队列是一个双端队列，支持在队列两端进行插入和删除操作。
2.单调队列的特点是队列中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
3.在插入新元素时，如果新元素破坏了当前的单调性，则在队尾删除一部分元素，直到满足单调性要求。这样可以保证队列中的元素保持单调性。
4.单调队列的典型应用是在滑动窗口中寻找最大/最小值的问题

单调队列的实现：

deque<int> que; // 使用deque来实现单调队列
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.push_back(value);

    }
    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() {
        return que.front();
    }

 题解：

 经典的滑动窗口问题，直接用单调递增队列，和单调递减队列即可，使队头元素为最大值或者是最小值，当超过范围k时从队头弹出元素

#include<iostream>
#include<deque>
#include<vector>
using namespace std;
int x;
struct sd
{
    int num, val; //存储编号和大小
};
deque<sd> que;
deque<sd> que1;
int add[3][1000005]; //用以存储答案的----见代码
int main()
{
    int n, m, k, cnt = 1;
    cin >> n >> k;
    sd rr;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);  //输入
        rr.num = i; rr.val = x;  //赋值
        while (!que.empty() && x >= que.back().val)
            que.pop_back();  //单调队列的操作，以保证单调
        while (!que1.empty() && x <= que1.back().val)
            que1.pop_back();
        que.push_back(rr); //压入队列
        que1.push_back(rr);//同上
        while (i - k >= que.front().num)  //T掉不在范围内的
            que.pop_front();
        while (i - k >= que1.front().num)
            que1.pop_front(); //同上
        if (i >= k)
        {
            add[0][cnt] = que.front().val;
            add[1][cnt] = que1.front().val;
            cnt++;
        } //存答案
    }
    for (int i = 1; i < cnt; i++)
        printf("%d ", add[1][i]);
    printf("\n");
    for (int i = 1; i < cnt; i++)
        printf("%d ", add[0][i]);  //输出
    return 0;
}

 图的储存和去重

将队列值用map存储起来，用c++自带函数对其进行去重，最后直接将不符合条件的弹出队列即可

#include<iostream>
#include<map>
#include<deque>
#include<algorithm>
using namespace std;
int t, n;
const int N = 2e5 + 15;
int k;
int a[N];
int main() {
	cin >> t;
	while (t--) {
		int ans = 0;
		deque<int>que;
		map<int, int>mp;
		cin >> n >> k;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			++mp[a[i]];
		}
		sort(a + 1, a + n + 1);
		int len = unique(a + 1, a + n + 1) - a - 1;
		int res = 0;
		for (int i = 1; i <= len; i++) {
			while (que.size() && i - que.front() + 1 > k) {
				res -= mp[a[que.front()]];
				que.pop_front();
			}
			while (que.size() && a[que.back()] != a[i] - 1) {
				res -= mp[a[que.back()]];
				que.pop_back();
			}
			res += mp[a[i]];
			que.push_back(i);
			ans = max(ans, res);
		}
		cout << ans << endl;
	}
	return 0;
}