题意

给一个长度为N的数组,一个长为K的滑动窗体从最左端移至最右端,你只能看到窗口中的K个数,找出窗口中的最大值和最小值,然后将窗口往后移动一位。

思路

找最大值和找最小值是一样的方法,这里以找最大值为例。
每次窗口向右移动时,如果进来了一个比上一个值要大的数,则上一个值从此以后绝不可能成为窗口中的最大值,也就是说,当窗口的右端点从移动到时,如果,那么再也不可能是窗口中的最大值
同时,因为窗口的移动,窗口左端点上的数会离开窗口,不再被我们考虑。

这样,我们可以考虑使用双向队列,每次移动窗口时从后往前删除不再可能成为最大值的数,并且判断最前面的数是否已经离开窗口
为了判断最前面的数是否已经离开窗口,我们可以在队列中不直接储存数的大小,而是储存数的下标,每次要比较的时候再用过下标找到数,这样会方便一些。

找最小值同理,判断不可能的数的时候把符号变一下就行了

代码

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;  //数组长度N
    int K;  //窗口长度K
    cin >> N >> K;
    int num[N + 5];
    for (int i = 1; i <= N; ++i) {
        cin >> num[i];
    }

    deque<int> maxIndex;  //记录当前窗口中最大值的下标
    deque<int> minIndex;  //记录当前窗口中最小值的下标
    vector<int> max;    //记录所有最大值
    vector<int> min;    //记录所有最小值
    maxIndex.push_back(1);
    minIndex.push_back(1);

    for (int i = 2; i <= N; ++i) {
        //维护最小值
        //如果新来的数比队列最后一个数小,把队列中最后一个数删掉
        while (!minIndex.empty() && num[i] < num[minIndex.back()]) {
            minIndex.pop_back();
        }
        //往队列里压入新来的数
        minIndex.push_back(i);
        //窗口移动后,队列最前面在窗口范围之外的数删掉
        while (minIndex.front() <= i - K) {
            minIndex.pop_front();
        }
        if (i >= K) {
            min.push_back(minIndex.front());
        }

        //维护最大值
        while (!maxIndex.empty() && num[i] > num[maxIndex.back()]) {
            maxIndex.pop_back();
        }
        maxIndex.push_back(i);
        while (maxIndex.front() <= i - K) {
            maxIndex.pop_front();
        }
        if (i >= K) {
            max.push_back(maxIndex.front());
        }
    }
    for (int &i:min) {
        cout << num[i] << " ";
    }
    cout << endl;
    for (int &i:max) {
        cout << num[i] << " ";
    }
    return 0;
}