栈：模板题(AcWing.828)

Java代码

import java.io.*;
public class Main{
    private static int tt = 0;
    private static int[] stk;
    private static final int N = 100010;
    //初始化
    static void init(){
        stk = new int[N];
    } 
    //向栈内添加元素
    static void push(int x){
        stk[++tt] = x;
    }
    //弹出栈顶元素
    static void pop(){
        tt--;
    }
    //判空
    static String empty(){
        if(tt == 0) return "YES";
        else return "NO";
    }
    //查询栈顶元素
    static int query(){
        return stk[tt];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        init();
        while(n-- > 0){
            String[] s = br.readLine().split(" ");
            if(s[0].equals("push")) push(Integer.parseInt(s[1]));
            else if(s[0].equals("pop")) pop();
            else if(s[0].equals("empty")) System.out.println(empty());
            else System.out.println(query());
        }
    }
}

队列(模板题：AcWing.829)

Java代码

import java.io.*;
public class Main{
    private static final int N = 100010;
    private static int[] q;
    private static int hh = 0;//队头
    private static int tt = -1;//队尾
    //初始化
    static void init(){
        q = new int[N];
    }
    //队尾插入元素
    static void push(int x){
        q[++tt] = x;
    }
    //队头弹出元素
    static void pop(){
        hh++;
    }
    //判空
    static String empty(){
        if(hh > tt) return "YES";
        else return "NO";
    }
    //查询队头元素
    static int query(){
        return q[hh];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        init();
        while(n -- > 0){
            String[] s = br.readLine().split(" ");
            if(s[0].equals("push")) push(Integer.parseInt(s[1]));
            else if(s[0].equals("pop")) pop();
            else if(s[0].equals("empty")) System.out.println(empty());
            else System.out.println(query());
        }
    }
}

单调栈(模板题：AcWing.830)

• 单调栈一般用来求数组中某个数左边/右边第一个比它小/大的数
  • 求左边第一个小于它的数：维护一个沿栈顶方向递增的栈，并从头到尾遍历数组
  • 求左边第一个大于它的数：维护一个沿栈顶方向递减的栈，并从头到尾遍历数组
  • 求右边第一个小于它的数：维护一个沿栈顶方向递增的栈，并从尾到头遍历数组
  • 求右边第一个大于它的数：维护一个沿栈顶方向递减的栈，并从尾到头遍历数组

Java代码

import java.io.*;
public class Main{
    private static int[] stk;
    private static int N = 100010;
    private static int tt = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        stk = new int[N];
        String[] s = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            int x = Integer.parseInt(s[i]);
            while(tt != 0 && x <= stk[tt]) tt--;
            if(tt == 0) System.out.print(-1 + " ");
            else System.out.print(stk[tt] + " ");
            stk[++tt] = x;
        }
    }
}

单调队列(模板题：AcWing.154)

Java代码

import java.io.*;
public class Main{
    private static int[] q;
    private static int N = 1000010;
    private static int hh = 0, tt = -1;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        q = new int[N];
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int[] a = new int[N];
        String[] s1 = br.readLine().split(" ");
        for(int i = 0; i < n; i++) a[i] = Integer.parseInt(s1[i]);
        for(int i = 0; i < n; i++){
            if(hh <= tt && i - m + 1 > q[hh]) hh++;
            while(hh <= tt && a[q[tt]] >= a[i]) tt--;
            q[++tt] = i;
            if(i-m >= -1) System.out.print(a[q[hh]] + " "); 
        }
        System.out.println();
        hh = 0;
        tt = -1;
        for(int i = 0; i < n; i++){
            if(hh <= tt && i - m + 1 > q[hh]) hh++;
            while(hh <= tt && a[q[tt]] <= a[i]) tt--;
            q[++tt] = i;
            if(i-m >= -1) System.out.print(a[q[hh]] + " "); 
        }
        System.out.println();
    }
}