滑动窗口题解
滑动窗口
https://ac.nowcoder.com/acm/problem/50528
看了邓老师的题解才知道这道是单调队列经典例题。
以前也没有接触过这个单调队列。自己一边学习巨佬们的代码一边思考问题，发现单调队列并不是想象中的那么难。
想明白了就觉得有些简单了。这次写题解就算是现学现卖吧。
答题思路就是维护一个单调队列，保证其队尾是最小值，并且队尾下标是在我们要查找的窗口中，那么我们应该怎样去维护呢？
这里我用一个q[]来作为单调队列的实现，head和tail作为队尾和队首的下标。
首先我们要让队尾下标小于队首下标，并且如果队首元素小于等于当前元素的话，就要往下找一个比当前元素大的然后替换。
这里用tail-1是因为之后tail会自增,需要-1才是队首元素。
之后再判断队尾元素是否在区间里，如果不在的话就丢掉往前找到第一个在此区间里的元素作为队尾元素。
最大值同理，只需要改几个符号即可。java代码如下。
import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
public static void main(String args[])throws IOException
{
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int n = (int)in.nval;
in.nextToken();
int k = (int)in.nval;
int min[] = new int[n+1];
int max[] = new int[n+1];
int num[] = new int[n+1];
int q[] = new int[n+1];
for(int i=1;i<=n;i++)
{
in.nextToken();
num[i] = (int)in.nval;
}
int head=0,tail=0;
for (int i = 1; i <= n; ++i)
{
while (head < tail && num[q[tail-1]] <= num[i]) tail--;
q[tail++] = i;
while (i > k && q[head] <= i-k) head++;
max[i] = num[q[head]];
}
head =0; tail = 0;
for (int i = 1; i <= n; ++i)
{
while (head < tail && num[q[tail-1]] >= num[i]) tail--;
q[tail++] = i;
while (i > k && q[head] <= i-k) head++;
min[i] = num[q[head]];
}
for(int i=k;i<=n;i++)
out.print(min[i]+" ");
out.println();
for(int i=k;i<=n;i++)
out.print(max[i]+" ");
out.flush();
}
}
Momenta公司福利 293人发布