A39805. 滑动窗口
填空题
困难
知识点
题目描述
滑动窗口
题目描述
给定一个长度为n（n<=10^6）的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
下面是一个例子：
数组是 [1 3 -1 -3 5 3 6 7]， k = 3。
你的任务是得到滑动窗口在每个位置时的最大值和最小值。
输入
输入包括两行。
第一行包括n和k，分别表示数组的长度和窗口的大小。
第二行包括n个数字。
输出
输出包括两行。
第一行包括窗口从左至右移动的每个位置的最小值。
第二行包括窗口从左至右移动的每个位置的最大值。
样例输入
8 3
1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
参考答案
#include <stdio.h>
#include <iostream>
#include <vector>
#include <set>
#define IOS_SPEED std::ios::sync_with_stdio(false)
using std::cin;
using std::cout;
using std::vector;
using std::multiset;
void interface(){
int nums, size;
int new_num;
vector<int> lib, min, max;
multiset<int> window;
IOS_SPEED;
cin >> nums >> size;
for(int i=0; i<nums; i++){
cin >> new_num;
lib.push_back(new_num);
}
for(int i=0; i<size; i++) window.insert(lib[i]);
min.push_back(*window.begin()); max.push_back(*window.rbegin());
for(int i=0; i<nums-size; i++){
auto it = window.find(lib[i]);
window.erase(it); window.insert(lib[i+size]);
min.push_back(*window.begin()); max.push_back(*window.rbegin());
}
bool first = true;
for(auto i: min){
if(!first) cout << " "; first = false; cout << i;
}
cout << "\n";
first = true;
for(auto i: max){
if(!first) cout << " "; first = false; cout << i;
}
cout << "\n";
lib.clear(); window.clear(); min.clear(); max.clear();
}
int main()
{
interface();
return 0;
}
上一题
下一题