输入样例
8 3
1 3 -1 -3 5 3 6 7
C++ 代码
#include<iostream>
#include<deque>
using namespace std;
const int N = 1000009;
int a[N],n,k;
deque<int> q,p;//定义两个队列,分别用来求最大值和最小值
int main()
{
cin >> n >> k;
for(int i = 0;i < n;i ++) cin >> a[i];
for(int i = 0;i < n;i ++) //最小值
{
if(q.size() && i - q.front() + 1 > k) q.pop_front();//队列不为空并且队头元素不在窗口里面
while(q.size() && a[q.back()] >= a[i]) q.pop_back();//不满足单调递增时,弹出队列尾元素
q.push_back(i);//当队列为空或满足单调递增时进入队列,进入队列的是数组a里元素的下标
if(i >= k - 1) cout << a[q.front()] << " ";//i从0开始所以i == k -1是第一次可以开始输出最大值
}
puts("");
for(int i = 0;i < n;i ++) //最大值,与最小值类似
{
if(p.size() && i - p.front() + 1 > k) p.pop_front();
while(p.size() && a[p.back()] < a[i]) p.pop_back();
p.push_back(i);
if(i >= k - 1) cout << a[p.front()] << " ";
}
puts("");
return 0;
}