算法竞赛入门第三节笔记

洛谷 P1886
POJ 2823
Sliding window（单调队列）
题目描述
有一个长为 n的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1,3,−1,−3,5,3,6,7]，and k=3
输入格式
输入一共有两行，第一行有两个正整数 n,k
第二行 n个整数，表示序列 a
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
输入
8 3
1 3 -1 -3 5 3 6 7
输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
看博客大佬们都说这是个入门题，身为菜鸡的我瑟瑟发抖，（数据结构从入门到放弃）差不多理解了一下午后还有点懵懂，之前好像没怎么接触过单调队列这方面的知识，以后还是要多多练习！
**题解：用数组模拟去维护一个单调队列，以求每次窗口滑动的最小值为例，我们需要去维护一个单调递减的队列，向队尾插入元素，如果有新元素入队，判断新元素与队尾元素的大小，如果新元素比队尾元素小，就删除队尾元素，继续比较，直到队尾元素小于新元素，再将新元素插到其后，保证每次队首都是最小值，由于序列中的元素只在给定的区间内有效，当队首元素不在滑动窗口内时，就删除队首元素
举个栗子：
8 3
1 3 -1 -3 5 3 6 7
输出的是-1 -3 -3 -3 3 3
下面我们来看一下是如何实现的：
队列中没有元素，元素1入队列，元素3大于队尾元素1，元素3入队列，元素-1小于队尾元素3，将3删除，小于队尾元素1，将1删除，-1入队列，此时下标已经达到k,（样例中的3），得到第一个最小值-1，此时队首为-1，元素-3小于-1，将-1删除，-3入队列，成为队首，因为此时只有-3一个元素了，所以-3也是队尾，记录最小值-3，元素5大于-3，入队列，记录最小值-3，元素3小于5，将5删除，元素3大于-3，元素3入队列，成为队尾，记录此时的队首即最小值-3，6大于队尾元素3,6入队列，此时-3已经出了滑动窗口里，-3自然被弹出了，记录此时的队首即为最小值3，7大于队尾元素6，7入队列，记录此时的队首即为最小值3
(for循环中的i往后动一个，必定输出一个该区间内的最小值）
AC代码：
这个代码在洛谷上过了，在poj上没试过

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000010];
int du[1000010];
int i;
int main()
{ 
  cin>>n>>k;
   for(i=1;i<=n;i++)
   scanf("%d",&a[i]);
   int l=0,r=1;//左边界和右边界 
   du[0]=1;//此数组用来记录下标
   if(k==1)
   printf("%d ",a[1]);
   for(i=2;i<=n;i++)
   { 
     if(r>l&&i-du[l]>=k)//判断是否在滑动窗口内
      l++;
      while(r>l&&a[i]<=a[du[r-1]])
      r--;//求最小值，如果队尾元素比新元素大，一直删除队尾元素。直到队尾元素比新元素小
      du[r++]=i;//将新元素加进来
      if(i>=k)
   printf("%d ",a[du[l]]);//输出队首
    
   }
   printf("\n");
   l=0;
   r=1;
   du[0]=1;//要记得重新初始化，原来的已经被覆盖了 
   if(k==1)
   printf("%d ",a[1]); 
   for(i=2;i<=n;i++)
      { if(r>l&&i-du[l]>=k)
         l++;
         while(r>l&&a[i]>=a[du[r-1]])
         r--;
         du[r++]=i;
         if(i>=k)
         printf("%d ",a[du[l]]);
      }  
}

文末，菜鸡叹息…