单调队列

题目大意：让我们从左到右，每次扫描k个长度，并找出这段子序列的最大值，依次输出并换行
解法：
一（50pts）：
很容易想到一种模拟的方法，用vector存下每次的元素，找出最大值：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) 
        cin >> nums[i];
        
    for (int i = 0; i <= n - k; i++) {
        int mx = nums[i];
        for (int j = i + 1; j < i + k; j++) {
            if (nums[j] > mx) {
                mx = nums[j];
            }
        }
        cout << mx << endl;
    }
    
    return 0;
}

代码非常短小，但是这种方只能通过5个点;
因为这道题的数据范围是1≤k≤n≤2×10 ^6,使用暴力枚举，时间复杂度是O(nk),严重超时。
二（100pts）:
那有没有一种数据结构能完整解决这道题呢？
首先考虑一种思路：使用一个“数组”并维持此“数组”的单调性，让数组的头是当前子序列的最大值，并向后单调递减,这样可以使数组的尾为当前序列的最小值，实现方法：将序列的下标放进数组之中，从数组的尾插入值，每次检查数组是否为空且新的元素是否大于数组的尾（因为要保持单调性）,如果大于那么弹出当前数组的尾，插入新值，接下来，如果当前数组的长度大于k，那么就要输出数组的头并弹出
这个数组的名字就叫单调队列,一般使用deque实现：

#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;

deque<int> dq;  // 单调队列，存储数组下标，保持对应元素值单调递减
int n, k;
const int maxn = 2e6 + 10;
int a[maxn];  // 存储输入数组

int main() {
	scanf("%d %d", &n, &k);  // 读取n个数，窗口大小为k
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);  // 读取数组元素
		
	for (int i = 1; i <= n; i++) {
		// 维护单调性：从队尾移除比当前元素小的元素下标
		while (!dq.empty() && a[dq.back()] < a[i])
			dq.pop_back();
			
		dq.push_back(i);  // 将当前下标加入队尾
		
		if (i >= k) {  // 当处理到第k个及以后的元素时，开始输出结果
			// 移除超出窗口范围的元素（窗口为[i-k+1, i]）
			while (!dq.empty() && dq.front() <= i - k)
				dq.pop_front();
				
			printf("%d\n", a[dq.front()]);  // 输出当前窗口最大值
		}
	}
	
	return 0;
}

时间复杂度O(n)，完全可以胜任这道题目