栈与队列专题详解之滑动窗口

题目描述 滑动窗口给定一个大小为 n ≤ 10^6 数组。有一个大小为 k 的滑动窗口它从数组的最左边移动到最右边。你只能在窗口中看到 k 个数字。每次滑动窗口向右移动一个位置。以下是一个例子该数组为 [1 3 -1 -3 5 3 6 7] k 为 3 。你的任务是确定滑动窗口位于每个位置时窗口中的最大值和最小值。输入格式输入包含两行。第一行包含两个整数 n 和 k 分别代表数组长度和滑动窗口的长度。第二行有 n 个整数代表数组的具体数值。同行数据之间用空格隔开。输出格式输出包含两个。第一行输出从左至右每个位置滑动窗口中的最小值。第二行输出从左至右每个位置滑动窗口中的最大值。输入样例8 3 1 3 -1 -3 5 3 6 7输出样例-1 -3 -3 -3 3 3 3 3 5 5 6 7解题代码#include bits/stdc.h using namespace std; int n,k,a[500010]; dequeintq; int main(){ scanf(%d%d,n,k); for(int i1;in;i) scanf(%d,a[i]); for(int i1;in;i){ if(!q.empty()i-q.front()k) q.pop_front(); while(!q.empty()a[i]a[q.back()]) q.pop_back(); q.push_back(i); if(ik) printf(%d ,a[q.front()]); } printf(\n); while(!q.empty()) q.pop_back(); for(int i1;in;i){ if(!q.empty()i-q.front()k) q.pop_front(); while(!q.empty()a[i]a[q.back()]) q.pop_back(); q.push_back(i); if(ik) printf(%d ,a[q.front()]); } }单调栈 / 单调队列还有更加广泛的运用例如某些动态规划问题需要使用单调队列进行优化这类问题将在动态规划专题中再展开介绍。