acwing 154滑动窗口

acwing 154滑动窗口

 

#include

using namespace std;

int n, k;

deque fax, fin;
vector num(1000010);

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen(".in", "r", stdin);

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> num[i];
    
    for (int i = 1; i <= n; i++)
    {
        if(fax.size())
            if (fax.front() < i - k + 1)
                fax.pop_front();

        if(fax.size())    
            while (fax.size() && num[fax.back()] > num[i])
            fax.pop_back();

        fax.push_back(i);
        if (i >= k)
            cout << num[fax.front()] << ' ';

    }

    cout << endl;
    for (int i = 1; i <= n; i++)
    {
        if (fin.size())
            if (fin.front() < i - k + 1)
                fin.pop_front();

        if (fin.size())
            while (fin.size() && num[fin.back()] < num[i])
                fin.pop_back();

        fin.push_back(i);
        if (i >= k)
            cout << num[fin.front()] << ' ';
    }
    
    return 0;
}