洛谷P1886 滑动窗口_第二次理解

---

第一次做的在这

---

思路：

之前讲这是一个“特殊的”单调栈，但其实，头尾都能进出的东西有名字——双端队列。

对于每一个数（大于等于k），要找到他之前（包括自己）的k个数里的最值 ，那就要：

1、找到该值在之前单调双端队列中的位置

2、先将该数入队

3、再去拿队头。

因为自己可能是最值。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e6+100;

ll n , k ;
ll a[N];

void solve(){
	cin>>n>>k ;
	for(ll i = 1 ; i <= n ; i ++ )cin>>a[i] ;
	deque<ll>q ;
	
	for( ll i = 1 ; i <= n ; i ++ ){
		while(q.size() && a[q.back()] >= a[i]){
			q.pop_back() ;//找到应该在的位置
		}
		q.push_back(i) ;
		
		if(q.size() && q.back() - q.front() >= k)q.pop_front() ;
		if(i >= k){
			cout<<a[q.front()]<<" ";
		}
		//for(auto x : q)cout<<a[x]<<" ";cout<<endl;
		
	}cout<<endl;
	
	q.clear() ;
	
		for( ll i = 1 ; i <= n ; i ++ ){
		while(q.size() && a[q.back()] <= a[i]){
			q.pop_back() ;
		}
		q.push_back(i) ;
		
		if(q.size() && q.back() - q.front() >= k)q.pop_front() ;
		if(i >= k){
			cout<<a[q.front()]<<" ";
		}
		//for(auto x : q)cout<<a[x]<<" ";cout<<endl;
		
	}
}

int main(){
	ios::sync_with_stdio(false);
	//freopen("inn.in","r",stdin) ;
	solve();
}