题意概括

给定一个整数数组 nums 和一个整数 k，存在一个大小为 k 的滑动窗口，它从数组的最左侧移动到最右侧。你只能看到窗口内的 k 个数字。滑动窗口每次向右移动一位。你的任务是返回一个数组，其中包含滑动窗口在每个位置时的最大值。

数据范围:

• $1 \le k \le n \le 10^5$ (假设)
• 数组元素的值在 int 范围内。

基础知识

本题是求解滑动窗口最大值的经典问题。如果采用朴素解法，即对每个窗口都遍历一次以寻找最大值，时间复杂度将是 $O(n \times k)$，在 $n$ 和 $k$ 较大时会超时。

更优的解法是使用 单调队列 (Monotonic Queue)，通常用一个 双端队列 (Deque) 来实现。这种方法可以将时间复杂度优化到 $O(N)$。

单调队列的核心思想是，维护一个队列，使其内部存储的 数组下标 所对应的 元素值 始终保持单调递减。这样，队列的头部（队首）元素就永远是当前窗口内的最大值的下标。

算法流程如下，遍历数组中的每个元素 a[i]：

1. 维护单调性（队尾操作）: 在将新元素 a[i] 的下标 i 加入队列之前，先从 队尾 移除所有下标对应的元素值小于等于 a[i] 的元素。这保证了队列的单调递减性，因为这些较小的元素在新元素 a[i] 进入窗口后，不可能成为最大值。

   while (!dq.empty() && a[dq.back()] <= a[i]) {
       dq.pop_back();
   }
   

2. 入队（队尾操作）: 将当前元素的下标 i 加入队尾。

   dq.push_back(i);
   

3. 移除过期元素（队首操作）: 检查队首的下标是否已经滑出当前窗口的范围（即下标小于 i - k + 1）。如果是，则从 队首 弹出该元素。

   if (dq.front() <= i - k) {
       dq.pop_front();
   }
   

4. 记录结果: 当窗口形成后（即 i >= k - 1），当前窗口的最大值就是队首下标对应的元素 a[dq.front()]。

通过这套机制，每个元素的下标最多进队一次、出队一次，因此总的时间复杂度为 $O(N)$，空间复杂度为 $O(k)$（队列中最多存储 k 个元素）。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

void run() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int k;
    cin >> k;

    deque<int> dq; // 存储下标的单调队列
    vector<int> ans;

    for (int i = 0; i < n; ++i) {
        // 1. 移除队尾小于等于当前元素的元素
        while (!dq.empty() && a[dq.back()] <= a[i]) {
            dq.pop_back();
        }

        // 2. 将当前元素下标入队
        dq.push_back(i);

        // 3. 移除队首已经滑出窗口的元素
        if (dq.front() <= i - k) {
            dq.pop_front();
        }

        // 4. 当窗口完全形成后，记录当前窗口的最大值
        if (i >= k - 1) {
            ans.push_back(a[dq.front()]);
        }
    }

    for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
8
1 3 -1 -3 5 3 6 7
3
输出:
3 3 5 5 6 7

样例 2:
输入:
2
9 11
2
输出:
11
*/