通过数组模拟单调栈

import java.util.Scanner;

public class Main {
    static int N=100010;
    public static void main(String[] args) {
        //单调栈
        //通过数组模拟栈
        int[] stk=new int[N];
        int tt=0;
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            int num=0;
            if(sc.hasNext()){
                num=sc.nextInt();
            }
            while(tt>=1&&num<=stk[tt]){
                tt--;
            }
            if(tt>=1){
                System.out.print(stk[tt]+" ");
            }else{
                System.out.print(-1+" ");
            }

            stk[++tt]=num;
        }
    }
}

数组模拟单调队列

滑动窗口最值

import java.util.Scanner;

public class Main {
    static  int N=1000010;
    //计算滑动窗口最值
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int k=sc.nextInt();
        //通过单调对列计算滑动窗口最值

        //将所有的元素保存
        int[] nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=sc.nextInt();
        }
        int[] queue=new int[N];
        int hh=0,tt=-1;
        for(int i=0;i<n;i++){
            //通过双端队列
            if(hh<=tt&&i-k+1>queue[hh]){
                hh++;
            }
            while(hh<=tt&&nums[queue[tt]]>=nums[i]){
                tt--;
            }
            //将当前元素放入队尾
            queue[++tt]=i;
            if(i>=k-1){
                System.out.print(nums[queue[hh]]+" ");
            }
        }
        System.out.println();
        hh=0;
        tt=-1;
        for(int i=0;i<n;i++){
            if(hh<=tt&&i-k+1>queue[hh]){
                hh++;
            }
            while(hh<=tt&&nums[queue[tt]]<=nums[i]){
                tt--;
            }
            queue[++tt]=i;
            if(i-k+1>=0){
                System.out.print(nums[queue[hh]]+" ");
            }
        }

    }

}