题目描述
啊 这 就这样吧 越来越想跳槽去c++了
import java.util.LinkedList;
import java.io.*;
public class Main{
public static int[] getMinWindow(int[] a,int w,int n){
if (a == null || w < 1 || a.length < w) {
return null;
}
// int n = a.length;
int[] min = new int[n-w+1];
int idx = 0 ;
LinkedList<Integer> q1 = new LinkedList<Integer>();
for(int i = 0 ; i < n ; i++){
while(!q1.isEmpty() && a[q1.peekLast()] >= a[i] ){
q1.pollLast();
}
q1.addLast(i);
if(q1.peekFirst() == i - w ){
q1.pollFirst();
}
if( i >= w - 1){
min[idx++] = a[q1.peekFirst()];
}
}
return min;
}
public static int[] getMaxWindow(int[] a,int w,int n) {
if (a == null || w < 1 || a.length < w) {
return null;
}
// int n = a.length;
int[] max = new int[n-w+1];
int idx = 0 ;
LinkedList<Integer> q1 = new LinkedList<Integer>();
for(int i = 0 ; i < n ; i++){
while(!q1.isEmpty() && a[q1.peekLast()] <= a[i] ){
q1.pollLast();
}
q1.addLast(i);
if(q1.peekFirst() == i - w ){
q1.pollFirst();
}
if( i >= w - 1){
max[idx++] = a[q1.peekFirst()];
}
}
return max;
}
public static void printArray(int[] a)throws IOException{
int n = a.length;
for(int i = 0 ; i < n ; i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] split = bf.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int w = Integer.parseInt(split[1]);
String[] s = bf.readLine().split(" ");
int[] a = new int[n];
for(int i = 0 ; i < n ; i++) a[i] = Integer.parseInt(s[i]);
printArray(getMinWindow(a,w,n));
printArray(getMaxWindow(a,w,n));
}
}