废话不多说，直接上题：

---

 

 

1597：【 例 1】滑动窗口

时间限制: 1000 ms         内存限制: 524288 KB

提交数: 167     通过数: 106 

【题目描述】

原题来自：POJ 2823

给一个长度为 N 的数组，一个长为 K 的滑动窗体从最左端移至最右端，你只能看到窗口中的 K 个数，每次窗体向右移动一位，如下图：

 

窗口	最小值	最大值
[1 3 −1] −3 5 3 6 7	−1	3
1 [3 −1 −3] 5 3 6 7	−3	3
1 3 [−1 −3 5] 3 6 7	−3	5
1 3 −1 [−3 5 3] 6 7	−3	5
1 3 −1 −3 [5 3 6] 7	3	6
1 3 −1 −3 5 [3 6 7]	3	7

 

你的任务是找出窗体在各个位置时的最大值和最小值。

【输入】

第 1 行：两个整数 N 和 K；

第 2 行：N 个整数，表示数组的 N 个元素(≤2×109 )；

 

【输出】

第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开；

第二行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。

 

【输入样例】

8 31 3 -1 -3 5 3 6 7

【输出样例】

-1 -3 -3 -3 3 33 3 5 5 6 7

【提示】

据范围与提示：

对于 20% 的数据，K≤N≤1000；

对于 50% 的数据，K≤N≤10⁵ ；

对于 100% 的数据，K≤N≤10⁶ 。

【来源】

　　这道题方法众多，小编就来一一讲解。

　　方法一：打暴力

　　文邹邹一点那就是模拟算法，直接在区间内查找，时间复杂度是O(nk)，看起来也很高了，所以我们不能使用这种方法。

　　方法二：线段树

　　线段树是个好东西，可惜小编不会。

　　方法三：动态规划

　　这是最适合这道题的，这是单调队列优化动态规划的基本题型之一。不过时间复杂度相当低，只有O(n)。

　　综上所述，小编就决定使用单调队列优化动态规划了。

　　那么什么是单调队列优化动态规划呢？动态规划这个东西相比大家都很了解，那么问题就在于单调队列是什么。先回顾一下，队列就像是平时排队买饭一样，排成了一个队伍，满足先进先出（先排队的先买饭，先离开队伍），那么单调队列就不一样了，就是说队列中的每一个数要么就是递增的，要么就是递减的。

　　但是这和动态规划有什么关系？

　　在动态规划中，常常会遇到求最值（最大最小之类）的问题，这就和单调队列有关系了，单调队列的队首元素一定是整个队列的最大（或最小）的。

　　好了，以题目为例，回归正题：

　　我们如何设计状态？和最长上升子序列一个想法，我们不妨用min[i]表示以第i个数为结尾的窗口内最小元素。

　　显然，我们会发现这样的情况（k=3）：比如说目前队列里第一个数是3，第二个数是5，当前的数是1，那么3和5都会被弹出队列，为什么呢？因为在3和5的有生之年，一定不会成为最小的了，1已经在队列里了。

　　max[i]也是如此，但要注意时刻维持队列内元素个数不超过k个。

　　代码如下：

　　

1 #include
     
       2 #define size 1000000 3 using namespace std; 4 int n,k,a[size],minn[size],maxn[size],num[size],q[size]; 5 //依次表示：个数，窗口长度，每个数，最小数的数组，最大数的数组，队列元素的编号，队列元素的值  6 inline void dp_min()//窗口最小数dp  7 { 8     int head=1,tail=0;//head>tail表示空队列  9     for(int i=1;i<=n;i++)10     {11         while(num[head]
      
       <=tail) head++;//将队列维持好数量 12         while(a[i]<=q[tail]&&head<=tail) tail--;//把不可能最小的弹出队列 13         q[++tail]=a[i];//加入队列 14         num[tail]=i;//记录元素编号 15         minn[i]=q[head];//队首元素一定是最小的 16     }17 }18 inline void dp_max()//窗口最大数dp （同上） 19 {20     int head=1,tail=0; 21     for(int i=1;i<=n;i++)22     {23         while(num[head]
       
        <=tail) head++;24         while(a[i]>=q[tail]&&head<=tail) tail--;25         q[++tail]=a[i];26         num[tail]=i;27         maxn[i]=q[head];28     }29 }30 int main()31 {32     cin>>n>>k;33     for(int i=1;i<=n;i++)34     cin>>a[i];35     dp_min();36     dp_max();37     for(int i=1+k-1;i<=n;i++)//注意不要多输出 38     cout<
        
         <<" ";39     cout<