90求调

P1886 滑动窗口 /【模板】单调队列

chenshenghui @ 2024-03-31 15:56:11

#include<bits/stdc++.h>
using namespace std;
int l[1000005];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i];
    }

    for (int i = 1; i <= n - k + 1; i++)
    {
        long long minn = 10000000000;
        for (int j = i; j <= i + k - 1; j++)
        {
            if (l[j] < minn)
            {
                minn = l[j];
            }
        }
        cout << minn << " ";
    }
    cout << "\n";
    for (int i = 1; i <= n - k + 1; i++)
    {
        long long maxn = -10000000000;
        for (int j = i; j <= i + k - 1; j++)
        {
            if (l[j] > maxn)
            {
                maxn = l[j];
            }
        }
        cout << maxn << " ";
    }
}

by liusir146 @ 2024-03-31 16:21:53

我是跑了两次单调队列


by liusir146 @ 2024-03-31 16:23:18

感觉时间复杂度有问题


|