P1886 最后一个点WA求条，悬一关

wyc0607 @ 2024-08-19 12:08:46

#include<bits/stdc++.h>
#define IAKIOI ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
int n,k;
int a[1000005];
deque<int> q;
main() {
    IAKIOI
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    int t=1;
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.back()>=a[i]) q.pop_back();
        q.push_back(a[i]);
        if(i-t>=k&&a[t]==q.front()){
            t++;
            q.pop_front();
        }
        if(i-t>=k&&a[t]!=q.front()) t++;
        if(i>=k) cout<<q.front()<<' ';
    }
    cout<<'\n';
    q.clear();
    t=1;
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.back()<=a[i]) q.pop_back();
        q.push_back(a[i]);
        if(i-t>=k&&a[t]==q.front()){
            t++;
            q.pop_front();
        }
        if(i-t>=k&&a[t]!=q.front()) t++;
        if(i>=k) cout<<q.front()<<' ';
    }
}

by pmkmzfuzsotqotmzs @ 2024-08-19 13:28:34

@wyc0607 这个代码的问题主要集中在处理滑动窗口的逻辑上，尤其是窗口的起始位置 t 和元素的删除逻辑上。以下是几个主要问题：

窗口的起始位置 t 的更新：

当前代码在检查是否需要更新窗口起始位置 t 时，有一些不必要的复杂性，特别是两次检查 if(i-t>=k) 语句。这不仅增加了代码的复杂度，也容易引入错误。 正确的方式是在每次迭代时，只要 i >= t + k，就移动 t 以确保 t 指向窗口的正确起点。

判断是否需要删除队列中的元素：

代码中删除最小值（最大值）队列头部元素的逻辑有问题。特别是在处理 t 更新后，可能会导致队列头部元素没有被正确删除。

逻辑的重复性：

代码中最大值和最小值的处理逻辑高度相似，但分别写了两遍。可以将这些逻辑提取为一个函数，避免代码重复。

by pmkmzfuzsotqotmzs @ 2024-08-19 13:29:25

AC代码

#include<bits/stdc++.h>
#define IAKIOI ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;

int n, k;
int a[1000005];
deque<int> min_deque, max_deque;

void sliding_window_min() {
    for(int i = 1; i <= n; i++) {
        // 移除不在窗口内的元素
        if(!min_deque.empty() && min_deque.front() < i - k + 1) {
            min_deque.pop_front();
        }
        // 移除队列中所有大于等于当前元素的元素
        while(!min_deque.empty() && a[min_deque.back()] >= a[i]) {
            min_deque.pop_back();
        }
        // 将当前元素的索引加入队列
        min_deque.push_back(i);
        // 输出当前窗口的最小值
        if(i >= k) {
            cout << a[min_deque.front()] << ' ';
        }
    }
    cout << '\n';
}

void sliding_window_max() {
    for(int i = 1; i <= n; i++) {
        // 移除不在窗口内的元素
        if(!max_deque.empty() && max_deque.front() < i - k + 1) {
            max_deque.pop_front();
        }
        // 移除队列中所有小于等于当前元素的元素
        while(!max_deque.empty() && a[max_deque.back()] <= a[i]) {
            max_deque.pop_back();
        }
        // 将当前元素的索引加入队列
        max_deque.push_back(i);
        // 输出当前窗口的最大值
        if(i >= k) {
            cout << a[max_deque.front()] << ' ';
        }
    }
    cout << '\n';
}

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

    sliding_window_min(); // 输出最小值
    sliding_window_max(); // 输出最大值
}

by wyc0607 @ 2024-08-19 14:03:18

@pmkmzfuzsotqotmzs 蟹蟹，已关

by wyc0607 @ 2024-08-19 14:05:45

本帖截