Quotes 在从左往右滑动窗口求最小值时，考虑右侧新加入一个元素aj时会发生什么。 假设区间中已经有的一个元素ai使得ai≥aj，那么aj离开窗口一定比ai要晚，且今后ai在队列里的时候aj也一直在队列里。 在ai剩下的生命里直到离开区间，aj永远比它小，ai再也不可能成为（唯一的）最小值了。

现实是残酷的，OIer 们是残忍的，ai 已经失去了成为（唯一）最小值的机会，OIer 们毫不留情地抛弃掉它

#include<bits/stdc++.h>
using namespace std;
int   a[100005],n,k;//读法：116+5 
int   q[100002],h=0,t=0;
int ans[100003];
void hs(){
	h=1,t=0;
	for(int rend=1;rend<=n;rend++){//the right end of window
	//rend is the array in a[]
		////STEP1
	//	h++;//why not this
		while(h<=t&&rend-q[h]+1>k){
			q[h]=0;
			h++;
		}
		while(h<=t&&>a[rend]){
			q[t]=0;
			t--;
		}//the q[] is always in order:small to big
		
		////STEP2
		q[++t]=rend;//record the array not value
		
		////STEP3
		if(rend>=k){//or itll CE
			ans[rend-k+1]=q[h];
		}
	}
	return;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	hs();	
	for(int i=1;i<=n-k+1;i++){
		cout<<a[ans[i]]<<" ";
	}
	cout<<endl;
	for(int i=1;i<=n;i++){
		ans[i]=0;
	}
	for(int i=1;i<=n;i++){
		a[i]=-a[i];
	}
	hs();
	for(int i=1;i<=n-k+1;i++){
		cout<<-a[ans[i]]<<" ";
	}
	return 0;
}

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

题目理解

这道题目要求我们处理一个长度为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;
}