基本信息项目内容题目编号、来源P1886 滑动窗口 / 洛谷训练层级A 模板题知识版块数据结构 / 单调队列 / 滑动窗口区间最值解题前 · 关键信号识别维度分析目标、约束、底层结构目标输出每个固定大小窗口内的最小值和最大值约束窗口大小固定为 k从左向右滑动底层结构固定窗口下的区间最值查询。数据规模n ≤ 10^6数组需开到 1000005数值范围较大使用 long long 防止溢出。候选算法和依据单调队列依据固定窗口求区间最值的经典模型每个元素仅入队、出队各一次复杂度 O(n)暴力 O(nk) 在 1e6 规模下必然超时。复杂度预判O(n)仅两次线性遍历数组无嵌套循环1e6 数据轻松通过。解题后 · 外化复盘从会一次到稳定会维度内容实现结构 / 核心思路分两次遍历数组分别用单调递增队列求最小值、单调递减队列求最大值队列只存数组下标方便判断是否滑出窗口队列里对应数值从小到大。如果队尾数字 ≥ 当前数字说明队尾永远不可能成为任何窗口最小值直接删掉r–最后把当前下标放进队列。剔除越界下标窗口最多容纳 k 个元素。如果队首下标距离当前 i 超过 k代表已经滑出窗口队首出队l。输出答案当 i k 时第一个完整窗口形成队列头部就是当前窗口最小值。错因回溯逻辑BUG / 代码实现BUG逻辑BUG把队列存数值而非下标无法判断窗口边界代码BUG求最大值前忘记重置 l1,r0队列残留数据导致答案错乱大数组定义在函数内引发栈溢出宏定义 long long 后仍写 int main 编译失败。边界和易错点1. n k 时仅输出一个数字2. 大数组必须定义为全局局部 1e6 数组会栈溢出3. 窗口越界判断条件是q[l] k i注意等号不能漏4.#define int long long必须搭配signed main()5. 最小值用递增队列、最大值用递减队列判断符号不要写反。下次看到什么信号我应该想到这个方法看到「固定大小的滑动窗口 求区间最小值/最大值 数据规模 1e5 以上暴力会超时」优先想到单调队列模板。AC 完整代码#includebits/stdc.husingnamespacestd;#defineintlonglongintn,k,l1,r0;inta[1000005],q[1000005];signedmain(){cinnk;for(inti1;in;i){cina[i];}for(inti1;in;i){while(lra[q[r]]a[i]){r--;}q[r]i;while(lrq[l]ki){l;}if(ik){couta[q[l]] ;}}cout\n;l1,r0;for(inti1;in;i){while(lra[q[r]]a[i]){r--;}q[r]i;while(lrq[l]ki){l;}if(ik){couta[q[l]] ;}}return0;}---
P1886 滑动窗口 单调队列模板题解
发布时间：2026/7/11 1:02:34
基本信息项目内容题目编号、来源P1886 滑动窗口 / 洛谷训练层级A 模板题知识版块数据结构 / 单调队列 / 滑动窗口区间最值解题前 · 关键信号识别维度分析目标、约束、底层结构目标输出每个固定大小窗口内的最小值和最大值约束窗口大小固定为 k从左向右滑动底层结构固定窗口下的区间最值查询。数据规模n ≤ 10^6数组需开到 1000005数值范围较大使用 long long 防止溢出。候选算法和依据单调队列依据固定窗口求区间最值的经典模型每个元素仅入队、出队各一次复杂度 O(n)暴力 O(nk) 在 1e6 规模下必然超时。复杂度预判O(n)仅两次线性遍历数组无嵌套循环1e6 数据轻松通过。解题后 · 外化复盘从会一次到稳定会维度内容实现结构 / 核心思路分两次遍历数组分别用单调递增队列求最小值、单调递减队列求最大值队列只存数组下标方便判断是否滑出窗口队列里对应数值从小到大。如果队尾数字 ≥ 当前数字说明队尾永远不可能成为任何窗口最小值直接删掉r–最后把当前下标放进队列。剔除越界下标窗口最多容纳 k 个元素。如果队首下标距离当前 i 超过 k代表已经滑出窗口队首出队l。输出答案当 i k 时第一个完整窗口形成队列头部就是当前窗口最小值。错因回溯逻辑BUG / 代码实现BUG逻辑BUG把队列存数值而非下标无法判断窗口边界代码BUG求最大值前忘记重置 l1,r0队列残留数据导致答案错乱大数组定义在函数内引发栈溢出宏定义 long long 后仍写 int main 编译失败。边界和易错点1. n k 时仅输出一个数字2. 大数组必须定义为全局局部 1e6 数组会栈溢出3. 窗口越界判断条件是q[l] k i注意等号不能漏4.#define int long long必须搭配signed main()5. 最小值用递增队列、最大值用递减队列判断符号不要写反。下次看到什么信号我应该想到这个方法看到「固定大小的滑动窗口 求区间最小值/最大值 数据规模 1e5 以上暴力会超时」优先想到单调队列模板。AC 完整代码#includebits/stdc.husingnamespacestd;#defineintlonglongintn,k,l1,r0;inta[1000005],q[1000005];signedmain(){cinnk;for(inti1;in;i){cina[i];}for(inti1;in;i){while(lra[q[r]]a[i]){r--;}q[r]i;while(lrq[l]ki){l;}if(ik){couta[q[l]] ;}}cout\n;l1,r0;for(inti1;in;i){while(lra[q[r]]a[i]){r--;}q[r]i;while(lrq[l]ki){l;}if(ik){couta[q[l]] ;}}return0;}---
