题目描述

blablabla

样例

#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;
#define int long long
const int N = 1000010;
deque<int> q;
int a[N];

signed main() {
    int n; cin >> n;
    int k; cin >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 计算滑动窗口的最小值
    for (int i = 1; i <= n; i++) {
        // 移除大于当前元素的元素
        while (q.size() && q.back() > a[i]) q.pop_back();
        q.push_back(a[i]);
        if(i - k >= 1 && q.front() == a[i-k]){
            q.pop_front();
        }
        // 输出当前窗口的最小值
        if (i >= k) cout << q.front() << " ";
    }
    cout << endl;

    q.clear();
    // 计算滑动窗口的最大值
    for (int i = 1; i <= n; i++) {
        // 移除小于当前元素的元素
        while (q.size() && q.back() < a[i]) q.pop_back();
        q.push_back(a[i]);
        // 输出当前窗口的最大值
        if(i - k >= 1){
            if(q.front() == a[i-k]) q.pop_front();
        }
        if (i >= k) cout << q.front() << " ";
    }

    return 0;
}

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla