题目描述

blablabla

样例

blablabla

算法1

#include <bits/stdc++.h>
using namespace std;
int n,k;

vector<int> min_window(vector<int> &nums,int k)
{
    vector<int> res;
    deque<int> q;
    for( int i = 0 ; i < n ; i++ )
    {
        if( q.size() && i - k +1 > q.front() ) q.pop_front();
        while( q.size() && nums[q.back()] >= nums[i] ) q.pop_back();
        q.push_back(i);

        if( i +1 >= k ) res.push_back( nums[q.front()]);
    }
    return res;
}
vector<int> max_window(vector<int> &nums,int k)
{
    vector<int> res;
    deque<int> q;
    for( int i = 0 ; i < n ; i++ )
    {
        if( q.size() && i - k +1 > q.front() ) q.pop_front();
        while( q.size() && nums[q.back()] <= nums[i] ) q.pop_back();
        q.push_back(i);

        if( i +1 >= k ) res.push_back( nums[q.front()]);
    }
    return res;
}
int main()
{

    vector<int> nums;

    cin >> n >> k;

    for( int i = 0 ; i < n ; i++ ) 
    {   
        int num;
        cin >> num;
        nums.push_back(num);
    }

    auto small = min_window(nums,k);
    auto  big  = max_window(nums,k);

    for( int i = 0 ; i < small.size() ; i++) cout << small[i]<<' ';
    puts("");
    for( int i = 0 ; i < big.size() ; i++ ) cout << big[i]<<' ';
    return 0;
}