java中对栈进行了包装，即new Stack()
把元素入栈：push(E)；把栈顶的元素“弹出”：pop()；取栈顶元素但不弹出：peek() (栈为空时抛异常)判断栈是否为空：isEmpty()
单调栈例题
https://www.acwing.com/problem/content/832/
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int []arr=new int[n]; for (int i = 0; i < n; i++) { arr[i]= sc.nextInt(); } //存储最后的结果 StringBuilder sb=new StringBuilder(); //new 一个栈出来 Stack<Integer> stack=new Stack<>(); for (int i : arr) { //stack.peek() 取栈顶元素但不弹出 while (!stack.empty() &&i<=stack.peek()) { //stack.pop() 把栈顶的元素“弹出” stack.pop(); } if(stack.empty()){ sb.append("-1 "); }else sb.append(stack.peek()+" "); //元素入栈 stack.push(i); } System.out.println(sb.toString()); } }
单调队列例题 滑动窗口
https://www.acwing.com/problem/content/156/
思路
利用单调队列解决问题
题目要求求出滑动窗口范围内所有的最大最小值，而且滑动窗口中数的操作也符合队列的性质，右移一位，队头出，队尾加，这正好符合单调队列的所有性质，单调队列的头部会保存当前窗口中的最小或者最大值。
本题数据模拟
q1单调递增队列 q2单调递减队列
窗口位置 队列q1 队列q2 最小值(q1队头) 最大值(q2队头)
[1 3 -1] -3 5 3 6 7 [2] [1, 2] a[2] = -1 a[1] = 3
1 [3 -1 -3] 5 3 6 7 [3] [1, 2, 3] a[3] = -3 a[1] = 3
1 3 [-1 -3 5] 3 6 7 [3, 4] [4] a[3] = -3 a[4] = 5
1 3 -1 [-3 5 3] 6 7 [3, 5] [4, 5] a[3] = -3 a[4] = 5
1 3 -1 -3 [5 3 6] 7 [5, 6] [6] a[5] = 3 a[6] = 6
1 3 -1 -3 5 [3 6 7] [5,6,7] [7] a[5] = 3 a[7] = 7
import java.io.*; public class Main { static int N=1000010; static int[]arr=new int[N]; static int[]q=new int[N]; static int hh=0,tt=-1; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); String []s=br.readLine().split(" "); int n=Integer.parseInt(s[0]),k=Integer.parseInt(s[1]); String []s1=br.readLine().split(" "); for (int i = 0; i < n; i++) { arr[i]=Integer.parseInt(s1[i]); } for (int i = 0; i < n; i++) { // 判断队头是否已经滑出窗口, 如果滑出窗口, 则弹出队首元素,维护窗口大小不超过 k, 每次值滑动一次, 所以可以使用 if if (hh<=tt && i-k+1>q[hh]) hh++; //寻找窗口最小值 while (hh<=tt &&arr[q[tt]]>=arr[i]) tt--; q[++tt]=i; if(i+1>=k) bw.write(arr[q[hh]]+" "); } bw.write("\n"); hh=0; tt=-1; for (int i = 0; i < n; i++) { if (hh<=tt && i-k+1>q[hh]) hh++; //寻找窗口最大值 while (hh<=tt &&arr[q[tt]]<=arr[i]) tt--; q[++tt]=i; if(i+1>=k) bw.write(arr[q[hh]]+" "); } bw.flush(); br.close(); bw.close(); } }
