题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//STL deque双向队列版本
#include <iostream>
#include <deque>

using namespace std;

const int N = 1e6;
int n, k, a[N];
deque<int> q;

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n; i++)
    {
        if (!q.empty() && i-k+1 > q.front()) q.pop_front();
        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
        q.push_back(i);
        if (i >= k-1) printf("%d ", a[q.front()]);
    }
    printf("\n");

    while (!q.empty()) q.pop_back();

    for (int i = 0; i < n; i++)
    {
        if (!q.empty() && i-k+1 > q.front()) q.pop_front();
        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);
        if (i >= k-1) printf("%d ", a[q.front()]);
    }
    printf("\n");

    return 0;
}