滑动窗口最大值和最小值问题

题目理解

这道题目要求我们处理一个长度为n的序列，使用一个大小为k的窗口从左向右滑动，每次滑动一个单位，输出每次滑动后窗口中的最小值和最大值。

解题思路

我们可以使用双端队列(deque)来高效解决这个问题。双端队列可以在两端进行插入和删除操作，非常适合维护滑动窗口的最值。

最小值队列思路

1、维护一个单调递增的双端队列，队首元素始终是当前窗口的最小值

2、当新元素比队尾元素小时，弹出队尾元素，保持队列单调性

3、检查队首元素是否已经不在当前窗口范围内，如果是则弹出

4、当窗口形成时(即i >= k-1)，记录当前最小值

最大值队列思路

1、维护一个单调递减的双端队列，队首元素始终是当前窗口的最大值

2、当新元素比队尾元素大时，弹出队尾元素，保持队列单调性

3、检查队首元素是否已经不在当前窗口范围内，如果是则弹出

4、当窗口形成时(即i >= k-1)，记录当前最大值

注释代码：

#include<bits/stdc++.h>
using namespace std;

int n, k, a[1000005], minans[1000005], maxans[1000005], p;
deque<int> mindeque, maxdeque; // 双端队列，分别用于求最小值和最大值

int main() {
    // 输入数据
    cin >> n >> k;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for(int i = 0; i < n; i++) {
        // 维护最小值队列：保持队列单调递增
        while(!mindeque.empty() && a[mindeque.back()] >= a[i]) 
            mindeque.pop_back(); // 弹出队尾比当前元素大的元素
        mindeque.push_back(i); // 将当前元素索引加入队列
        
        // 维护最大值队列：保持队列单调递减
        while(!maxdeque.empty() && a[maxdeque.back()] <= a[i]) 
            maxdeque.pop_back(); // 弹出队尾比当前元素小的元素
        maxdeque.push_back(i); // 将当前元素索引加入队列
        
        // 检查队首元素是否已经不在当前窗口范围内
        while(!mindeque.empty() && mindeque.front() <= i - k)
            mindeque.pop_front(); // 弹出超出窗口范围的元素索引
        while(!maxdeque.empty() && maxdeque.front() <= i - k)
            maxdeque.pop_front(); // 弹出超出窗口范围的元素索引
        
        // 当窗口形成时(i >= k-1)，记录当前窗口的最小值和最大值
        if(i > k - 2) {
            minans[p] = a[mindeque.front()]; // 队首元素就是当前窗口最小值
            maxans[p++] = a[maxdeque.front()]; // 队首元素就是当前窗口最大值
        }
    }

    // 输出结果
    for(int i=0;i<p;i++)printf("%d ",minans[i]);
    printf("\n");
    for(int i=0;i<p;i++)printf("%d ",maxans[i]);
    //完结撒花
    return 0;
}

复杂度分析

时间复杂度：O(n)，每个元素最多入队和出队一次

空间复杂度：O(n)，用于存储结果和双端队列

关键点说明

1、双端队列中存储的是元素的索引而不是值而是位置，这样可以方便判断元素是否在窗口内

2、维护队列的单调性是核心，最小值队列保持递增，最大值队列保持递减

3、每次滑动窗口时，只需要检查队首元素是否过期，而不需要检查整个队列

这种方法比暴力解法(时间复杂度O(nk))高效得多，特别适合处理大规模数据。

正常代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],minans[1000005],maxans[1000005],p;
deque<int>mindeque,maxdeque;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        while(!mindeque.empty()&&a[mindeque.back()]>=a[i])mindeque.pop_back();
        mindeque.push_back(i);
        while(!maxdeque.empty()&&a[maxdeque.back()]<=a[i])maxdeque.pop_back();
        maxdeque.push_back(i);
        while(!mindeque.empty()&&mindeque.front()<=i-k)mindeque.pop_front();
        while(!maxdeque.empty()&&maxdeque.front()<=i-k)maxdeque.pop_front();
        if(i>k-2)minans[p]=a[mindeque.front()],maxans[p++]=a[maxdeque.front()];
    }
    for(int i=0;i<p;i++)printf("%d ",minans[i]);
    printf("\n");
    for(int i=0;i<p;i++)printf("%d ",maxans[i]);
    return 0;
}