1 条题解

  • 0
    @ 2026-11-16 20:48:26

    窗口极值索引:解题说明

    维护两个保存下标的 deque<int>,一个对应非递减值,另一个对应非递增值。扫描右端点 i,先从队头删除下标小于当前左端点的旧元素,再从最小队列尾部删除值严格大于 a[i] 的元素,从最大队列尾部删除值严格小于 a[i] 的元素,然后插入 i。

    被尾部删除的下标比 i 早且值更差;只要它仍在未来窗口中,i 也在窗口中,因此它永远不会成为需要的极值。相等值必须保留,队头就是所有极值候选中最早的下标。删除过期项后,两个队头分别给出要求的最小、最大及最靠左位置。

    具体接口是 empty、front、back、pop_front、pop_back、push_back。每个下标在每个队列中至多入队一次、出队一次,总时间 O(n),辅助空间 O(k),另有 O(n) 数组空间。

    常见错误:删除相等值而保留最晚位置;过期判断写错一位;输出队列中的位置而不是原数组下标;把 0 基下标直接输出;遗漏 k=1 或 k=n 的边界。

    验证期望由独立 Python 算法生成,不读取参考程序。样例先手算,再以空实现确认测试失败;正式数据包含边界、固定种子随机及两个最大规模用例。

    C++17 参考实现

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n,k; cin>>n>>k; vector<long long> a(n);
        for(auto &x:a) cin>>x;
        deque<int> low,high;
        for(int i=0;i<n;++i) {
            while(!low.empty()&&low.front()<=i-k) low.pop_front();
            while(!high.empty()&&high.front()<=i-k) high.pop_front();
            while(!low.empty()&&a[low.back()]>a[i]) low.pop_back();
            while(!high.empty()&&a[high.back()]<a[i]) high.pop_back();
            low.push_back(i); high.push_back(i);
            if(i>=k-1) cout<<a[low.front()]<<' '<<low.front()+1<<' '
                         <<a[high.front()]<<' '<<high.front()+1<<'\n';
        }
        return 0;
    }
    
    
    • 1

    信息

    ID
    5271
    时间
    2000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者