【Acwing】154滑动窗口

本文主要是介绍【Acwing】154滑动窗口，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

#include<bits/stdc++.h>
using namespace std;int n,k;
int nums[1000010] = {0};int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin>>n>>k;// 下面求最小值int cnt = 0;int res[1000010] = {0};deque<int> q; // 双端队列 for(int i=0;i<n;++i){// 输入数据cin>>nums[i];// 第一步：入。// 将nums[i]存入队列中，存入前进行下列操作，去除冗余元素while(!q.empty() && nums[i] < nums[q.back()]){q.pop_back();} q.push_back(i);// 第二步：出。// 将超出滑动窗口范围的数删掉if(i - q.front() + 1 > k){q.pop_front();}// 第三步：记录答案。if(i + 1 >= k){res[cnt++] = nums[q.front()]; }}for(int i=0;i<cnt;++i) cout<<res[i]<<' ';cout<<'\n';// 下面求最大值cnt = 0;q.clear();for(int i=0;i<n;++i){while(!q.empty() && nums[i] > nums[q.back()]){q.pop_back();} q.push_back(i);if(i - q.front() + 1 > k){q.pop_front();}if(i + 1 >= k){res[cnt++] = nums[q.front()]; }}for(int i=0;i<cnt;++i) cout<<res[i]<<' ';
}

这篇关于【Acwing】154滑动窗口的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---