1 条题解
-
0
窗口极值索引:解题说明
维护两个保存下标的
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
- 上传者