【每日一题】3月30日滑动窗口

戳我传送

题意：

给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，你的任务是找出窗体在各个位置时的最大值和最小值。

思路：
就和邓老师说的那样，每次滑动一个区间，区间从[l,r]到[l+1,r+1]，只是增加了a[r+1]减少了a[l]，所以完全没有必要重新扫一遍区间。以最大值为例：
1.将新进入区间的这个元素往双端队列里放，但放进来之前需要判断队尾（也就是还有可能成为最大值的最后一个元素）是不是小于他小于他，如果是，就把这个队尾删掉（r- -），一直到前一个元素大于等于它为止。这样得出来的队列实际是单调递减的。
2.可以输出时先判断队首的元素是否在这个区间的范围内，如果不在，就把它删掉（l++）。
3.这个元素就一定是区间最大值吗，是的，1不是说了是单调递减的吗，当前取出来的数一定是这个区间最大的，比它大的数不在这个区间的范围内，一个区间内比最大值大的数在队列里都是存在最大值后面，最大值前面的数不会存在队列里面。
4.这个数一定是这个区间的吗，首先2可以保证这个数是在区间内的，由3又知道是最大值。
5.因为加入的元素是这个区间内的，而输出是在加入之后进行的（我的代码是这样），这个元素可能是这个区间的最大值也可能是下一个区间的最大值，所以这个区间的答案一定在队首。
还是表达不清楚，凑合着代码看吧，当时看这个代码看了好久才懂，我发现兰子大佬的代码没考虑k=1都可以A。
邓老师的代码有个地方有点多余，” if (i - du[l] >= m && (l < r)) l++ “。我一直搞不懂为什么既要队首考虑在范围内，又要保证队首不超过队尾，这就有点可能无解的意思，但是后面又有输出，我才发现只要保证队首在范围内就可以了，队首不会超过队尾的，也就是一定有解的。
Code：

#include<bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
int dp[1000010],a[1000010],n,k;
int main() {
    read(n),read(k);
    for(int i=1;i<=n;++i) read(a[i]);
    int l=0,r=0;
    dp[r++]=1;
    if(k==1)    printf("%d ",a[1]);
    for(int i=2;i<=n;++i) {
        while(r>l&&a[dp[r-1]]>a[i]) --r;
        dp[r++]=i;
        while(dp[l]<=i-k) ++l;
        if(i>=k)    printf("%d ",a[dp[l]]);
    }
    puts("");
    l=r=0;
    dp[r++]=1;
    if(k==1)    printf("%d ",a[1]);
    for(int i=2;i<=n;++i) {
        while(r>l&&a[dp[r-1]]<a[i]) --r;
        dp[r++]=i;
        while(dp[l]<=i-k) ++l;
        if(i>=k)    printf("%d ",a[dp[l]]);
    }
    puts("");
}