题解 | Sliding Window_单调栈实现O(n)更新

#include <iostream>
#include<bits/stdc++.h>
#include <vector>
using namespace std;

int main() {
    // int a, b;
    // while (cin >> a >> b) { // 注意 while 处理多个 case
    //     cout << a + b << endl;
    // }
    deque<int> inc, dec;
    int n, k, ele;
    cin >> n >> k;
    vector<int> nums;
    for(int i=0;i<n;++i) {
        cin >> ele;
        // cout<<ele<<" ";
        nums.emplace_back(ele);
    }
    vector<int> resultMin(n-k+1),resultMax(n-k+1);

    // cout<<endl;
    auto getMinWindow = [&]() {
        // vector<int> result(n - k + 1);
        // int tmp = k;
        for (int i = 0; i < k; ++i) {
            // cout<<i<<endl;
            while (!inc.empty() && nums[inc.back()] >= nums[i])inc.pop_back();
            inc.emplace_back(i);
        }
        resultMin[0] = nums[inc.front()];
        for (int i = 1; i <= n - k; ++i) {
            while (!inc.empty() && inc.front() < i)inc.pop_front();
            while (!inc.empty() && nums[inc.back()] >= nums[i + k - 1])inc.pop_back();
            inc.emplace_back(i+k-1);
            resultMin[i] = nums[inc.front()];
        }
        // cout<<resultMin.size()<<endl;
        // return result;
        return;
    };
    auto getMaxWindow = [&]() {
        vector<int> result(n - k + 1);
        int tmp = k;
        for (int i = 0; i < k; ++i) {
            while (!dec.empty() && nums[dec.back()] <= nums[i])dec.pop_back();
            dec.emplace_back(i);
        }
        resultMax[0] = nums[dec.front()];
        for (int i = 1; i <= n - k; ++i) {
            while (!dec.empty() && dec.front() < i)dec.pop_front();
            while (!dec.empty() && nums[dec.back()] <= nums[i + k - 1])dec.pop_back();
            dec.emplace_back(i+k-1);
            resultMax[i] = nums[dec.front()];
        }
        // return result;
        return;
    };
    getMinWindow();
    getMaxWindow();
    for(auto i:resultMin)printf("%d ",i);
    printf("\n");
    for(auto i:resultMax)printf("%d ",i);
    return 0;
}
// 64 位输出请用 printf("%lld")