NC50528 滑动窗口

#include <iostream>
using namespace std;
const int maxn = 1000010;
int arr[maxn];
int du[maxn];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    int l = 0;
    int r = 1;
    du[0] = 1;
    //if (k == 1)cout << arr[1]<<" ";
    for (int i = 2; i <= n; i++) {
        if (i - du[l] >= k&& (l < r))l++;
        while (l < r && arr[du[r - 1]] >= arr[i])r--;
        du[r++] = i;
        if (i >= k)cout << arr[du[l]] << " ";
  }
    cout << endl;
    l = 0;
    r = 1;
    du[0] = 1;
    for (int i = 2; i <= n; i++) {
        if (i - du[l] >= k && (l < r))l++;
        while (r > l && arr[du[r - 1]] <= arr[i])r--;
        du[r++] = i;
        if (i >= k)cout << arr[du[l]] << " ";
    }
}