蓝桥杯---附近最小(典型的滑动窗口类型问题)

时间:2024-03-14 10:51:21
import java.util.ArrayDeque; import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 public class Main { static int n; static int[] a; static int k; public static void main(String[] args) { Scanner scanner=new Scanner(System.in); n=scanner.nextInt(); a=new int[n+1]; for(int i=1;i<=n;i++){ a[i]=scanner.nextInt(); } k=scanner.nextInt(); ArrayDeque<Integer> q=new ArrayDeque<>();//双向队列 //维持队列的单调性,最小的在队头 for(int i=1;i<=k+1;i++){ while(!q.isEmpty()&&i<n&&a[i]<a[q.peekLast()]){ q.removeLast(); } q.addLast(i); } int[] mi=new int[n+1];//表示第i处的相应区间的最小值 mi[1]=q.peekFirst(); for(int i=2;i<=n;i++){ //先看左边界有没有超出 if(!q.isEmpty()&&q.peekFirst()<i-k&&i-k>0){ q.removeFirst(); } while(!q.isEmpty()&&i+k<=n&&a[i+k]<=a[q.peekLast()]){ q.removeLast(); } //这个地方出过错,着重标记 //后面添加的元素都是i+k,而不是i if(i+k<=n){ q.addLast(i+k); } mi[i]=q.peekFirst(); } for(int i=1;i<=n;i++){ System.out.print(a[mi[i]]+" " ); } } }