滑动窗口模板(Java)
题目描述
有一个长为 𝑛 的序列 𝑎，以及一个大小为 𝑘 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列 [1,3,−1,−3,5,3,6,7] 以及 𝑘=3，有如下过程：
输入格式
输入一共有两行，第一行有两个正整数 𝑛,𝑘。 第二行 𝑛 个整数，表示序列 𝑎
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
代码:
package lanqiao;import java.util.*;public class Main {static int N = 1000010;static int[] f1 = new int[N];static int[] f2 = new int[N];static int[] a = new int[N];static int h = 1,t = 1;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();for(int i = 1;i <= n;i ++){a[i] = sc.nextInt();}//求最小值f1[1] = 1;for(int i = 1;i <= n;i ++){if(f1[h] <= i - k) h ++;while(t >= h && a[f1[t]] >= a[i]) t --;f1[++t] = i;if(i >= k){System.out.print(a[f1[h]] + " ");}}System.out.println();//求最大值f2[1] = 1;for(int i = 1;i <= n;i ++){if(f2[h] <= i - k) h ++;while(t >= h && a[f2[t]] <= a[i]) t--;f2[++t] = i;if(i >= k){System.out.print(a[f2[h]] + " ");}}}
}