题目描述
现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
输入输出格式
输入格式：
输入一共有两行，第一行为n,k。
第二行为n个数(<INT_MAX).
输出格式：
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
8 3 1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3 3 3 5 5 6 7
说明
50%的数据，n<=10^5
100%的数据，n<=10^6//第一次数组只开到十万，才有60分(不是说50分的吗)
解题思路
一道RMQ裸题，做法很多，我用的是单调队列。单调队列跑两遍，分别求出区间最大值、区间最小值（其实不用记录答案统一输出的），边求边输出。单调队列我是看百度百科加神犇们博客上的代码看懂的，真的很好懂。
AC以后翻看了洛谷这题5页的AC记录，外加百度一下找到的解法，总结一下RMQ有以下几种解法
1、暴力——不说了
2、单调队列——跑得又快，代码又短，这题AC用时在1000ms~2000ms人丑常数大。记录里普遍在1300ms到16000ms，在这范围之外的很少，我的1428ms。
3、ST表(稀疏表，你要说是DP也行)——类似于倍增，记录一个个区间长度为1、2、4、8…的区间最值然后@#￥%，代码也挺简短我不会，正常写法$O(nlogn)$预处理(听说可以达到$O(n)$)，然后$O(1)$查询(听说标准应该是$O(\log_2(\log_2n))，和$O(1)$差不多，就成$O(1)$了)。
4、利用区间最值区间加性质的一系列数据结构
a、线段树——作用大，RMQ裸题杀鸡用牛刀了，记录里普遍3000ms～7000ms(预处理真慢)。
b、树状数组——记录里前几页没翻到，用题解里的代码测试了一下，居然才90分，一个点TLE了他的树状数组常数真大。就算这个点是1500ms吧，那总共耗时3526ms。
c、zkw线段树——神奇的数据结构我不会，作用同样巨大，题解里的代码2410ms。
5、最高端的做法——建一棵笛卡尔树#$%^#@，然后对每个询问在树上求一波LCA^@%%@%……好复杂我不会。
源代码
#include<stdio.h> #include<string.h> int a[1000010]={0},n,k; int q[1000010]={0},l=1,r=1; int main() { scanf("%d%d",&n,&k); l=1,r=1;memset(q,0,sizeof(q)); for(int i=1;i<=n;i++) scanf("%d",a+i); for(int i=1;i<=n;i++) { while(l<r&&a[q[r-1]]>a[i]) r--; q[r++]=i; while(l<r&&q[l]<=i-k) l++; if(i>=k) printf("%d ",a[q[l]]); } printf("\n"); l=1,r=1;memset(q,0,sizeof(q)); for(int i=1;i<=n;i++) { while(l<r&&a[q[r-1]]<a[i]) r--; q[r++]=i; while(l<r&&q[l]<=i-k) l++; if(i>=k) printf("%d ",a[q[l]]); } printf("\n"); return 0; }
