b2b网站怎么注册厦门seo代理商
例题
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1,3,−1,−3,5,3,6,7],and k=3。
输入格式
输入一共有两行，第一行有两个正整数 n,k。 第二行 n 个整数，表示序列 a
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
输入
8 3 1 3 -1 -3 5 3 6 7
输出
-1 -3 -3 -3 3 3 3 3 5 5 6 7
说明/提示
【数据范围】
对于 50%50% 的数据，1≤n≤105；
对于 100%100% 的数据，1≤k≤n≤106，ai∈[−2^31,2^31)。
代码实现
#include<iostream>
#include<queue>
using namespace std;
const int N=1e6+10;
int a[N],b[N],ans1[N],ans2[N];int main(){int n,m,c=0;cin>>n>>m;deque<int>s1,s2;for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];while(s1.size()&&a[s1.back()]>a[i])s1.pop_back();while(s2.size()&&b[s2.back()]<b[i])s2.pop_back();s1.push_back(i);s2.push_back(i);while(s1.front()<=i-m)s1.pop_front();while(s2.front()<=i-m)s2.pop_front();if(i>=m){ans1[++c]=a[s1.front()];ans2[c]=b[s2.front()];}}for(int i=1;i<=c;i++)cout<<ans1[i]<<" ";cout<<endl;for(int i=1;i<=c;i++)cout<<ans2[i]<<" ";cout<<endl;return 0;
} 滑动窗口模板
//求窗口内的最小值
deque<int>q;
for(int i=1;i<=n;i++){scanf("%d",&a[i]);//如果新元素小于尾部元素，就把尾部元素删除 while(q.size()&&a[q.back()]>a[i])q.pop_back();//把新元素的下标加入队列尾部q.push_back(i); //如果第一个元素的下标超出窗口范围，就把第一个元素删除 while(q.front()<=i-m)q.pop_front(); if(i>=m)printf("%d\n",a[q.front()]); } 双端队列常用操作
| 函数成员 | 函数功能 |
|---|---|
| begin() | 返回指向容器中第一个元素的迭代器。 |
| end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。 |
| rbegin() | 返回指向最后一个元素的迭代器。 |
| rend() | 返回指向第一个元素所在位置前一个位置的迭代器。 |
| cbegin() | 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| cend() | 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crbegin() | 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crend() | 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| size() | 返回实际元素个数。 |
| max_size() | 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。 |
| resize() | 改变实际元素的个数。 |
| empty() | 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
| shrink _to_fit() | 将内存减少到等于当前元素实际所使用的大小。 |
| at() | 使用经过边界检查的索引访问元素。 |
| front() | 返回第一个元素的引用。 |
| back() | 返回最后一个元素的引用。 |
| assign() | 用新元素替换原有内容。 |
| push_back() | 在序列的尾部添加一个元素。 |
| push_front() | 在序列的头部添加一个元素。 |
| pop_back() | 移除容器尾部的元素。 |
| pop_front() | 移除容器头部的元素。 |
| insert() | 在指定的位置插入一个或多个元素。 |
| erase() | 移除一个元素或一段元素。 |
| clear() | 移出所有的元素，容器大小变为 0。 |
| swap() | 交换两个容器的所有元素。 |
| emplace() | 在指定的位置直接生成一个元素。 |
| emplace_front() | 在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。 |
| emplace_back() | 在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。 |