HJ176 【模板】滑动窗口

张开发
• 2026/4/13 23:30:13 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

HJ176 【模板】滑动窗口
题目题解(21)讨论(8)排行中等 通过率49.56% 时间限制3秒 空间限制256M知识点双指针校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述给定一个长度为 nn 的整数数组 aa 和一个窗口大小 kk (1≦k≦n)(1≦k≦n)。滑动窗口从左到右移动每次右移一位窗口覆盖下标 [i,ik−1][i,ik−1]。对于数组的每一个窗口位置求出窗口内元素的最大值。输入描述第一行输入两个整数 n,k(1≦k≦n≦2×105)n,k(1≦k≦n≦2×105)。第二行输入 nn 个整数 a1,a2,…,ana1​,a2​,…,an​元素范围 1≦ai≦1091≦ai​≦109。输出描述输出共 n−k1n−k1 个整数为每个滑动窗口的最大值数之间以单个空格分隔。示例1输入10 3 2 13 6 19 15 13 17 9 19 13复制输出13 19 19 19 17 17 19 19复制示例2输入10 1 13 13 5 3 9 19 18 4 17 3复制输出13 13 5 3 9 19 18 4 17 3复制示例3输入10 10 15 20 5 20 19 1 4 18 14 15复制输出20#include iostream #include vector using namespace std; int main() { //输入数据 int n, k; cin n k; vectorint a;//接受数组 for(int i 0; i n; i){ int tmp; cin tmp; a.push_back(tmp); } //双指针遍历序列a,同时用loc指针记录历史最大值位置 int loc -1; int left 0; int right k - 1; while(right n){ int max 0;//存储最大值 if(loc left){//loc还在窗口内只需要比较最新的值和loc指向的值的大小并更新max和loc的值 max a.at(loc); if(a.at(right) max){ max a.at(right); loc right; } } else{//loc不在窗口内就遍历新窗口获取max值并更新loc值 for(int j left; j right; j){ if(a.at(j) max){ max a.at(j); loc j; } } } cout max ; left; right; } cout endl; return 0; } // 64 位输出请用 printf(%lld)

更多文章