题目链接：https://www.luogu.com.cn/problem/P2032

滑动窗口最大值问题题解

题目分析

题目要求我们找出一个1×n矩阵中，每个连续k个元素组成的子数组的最大值。木板从位置1开始，每次右移一位，直到覆盖最后k个元素，需要输出n-k+1个结果。

转换后其实就是：给定一个长度为n的数组和一个长度为k的滑动窗口，窗口从数组左端移动到右端，每次移动一个位置。需要求出每个窗口位置对应的窗口内最大值。

解题思路

暴力解法是对每个窗口遍历k个元素找最大值，时间复杂度O(n×k)，在大数据量下(如n=2×10^6)会超时。所以我们采用更高效的解法——单调队列（Monotonic Queue）。

核心算法：单调队列

使用单调递减队列来维护当前窗口内的潜在最大值候选元素。

算法原理

1. 单调队列性质：队列中的元素索引对应的数组值是单调递减的
2. 队列维护： 当新元素加入时，从队列尾部移除所有小于等于当前元素的索引保持队列头部始终是当前窗口内的最大值的索引
3. 窗口滑动： 检查队列头部索引是否已超出窗口范围，如果是则移除当窗口完整时（i ≥ k-1），记录当前最大值

代码实现详解

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

vector<int> vec(2000001);  // 存储输入数组
vector<int> Q(2000001);    // 单调队列（存储索引）
vector<int> ans(2000001);  // 存储每个窗口的最大值
int n, k, l, r;           // l,r分别指向队列的头部和尾部

int main() {
    cin >> n >> k;
    l = 0, r = 0;  // 初始化队列为空
    
    // 读入数组元素
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    
    // 处理前k-1个元素，构建初始单调队列
    for (int i = 0; i < k - 1; i++) {
        // 维护队列单调性：移除尾部所有小于等于当前元素的索引
        while (l < r && vec[Q[r - 1]] <= vec[i])
            r--;
        Q[r++] = i;  // 将当前索引加入队列尾部
    }
    
    // 处理剩余元素，同时记录每个窗口的最大值
    for (int i = k - 1; i < n; i++) {
        // 维护队列单调性
        while (l < r && vec[Q[r - 1]] <= vec[i])
            r--;
        Q[r++] = i;
        
        // 记录当前窗口的最大值（队列头部对应的值）
        ans[i - k + 1] = vec[Q[l]];
        
        // 检查队列头部是否已超出窗口范围
        if (Q[l] == i - k + 1)
            l++;
    }
    
    // 输出所有窗口的最大值
    for (int i = 0; i < n - k + 1; i++) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}

关键步骤解析

1. 单调队列维护

while (l < r && vec[Q[r - 1]] <= vec[i])
    r--;
Q[r++] = i;

• 目的：保持队列中索引对应的值是递减的
• 效果：新元素会"淘汰"所有比它小的旧元素

2. 窗口范围检查

if (Q[l] == i - k + 1)
    l++;

• 原理：如果队列头部索引等于即将离开窗口的索引，需要移除
• 保证：队列头部始终在当前窗口范围内

复杂度分析

• 时间复杂度：O(n) 每个元素最多入队一次、出队一次均摊时间复杂度为O(1) per element
• 空间复杂度：O(n) 使用三个长度为n的数组：