【算法基础】2.1栈和队列（单调栈和单调队列）

news/2024/5/19 19:14:30/文章来源:https://blog.csdn.net/qq_43406895/article/details/131726991

文章目录

例题
- 3302. 表达式求值（栈的应用）😭😭😭😭😭
- 830. 单调栈
- - 知识点
  - 解法
- 154. 滑动窗口（单调队列）
- - 知识点
  - 解法
相关链接 & 相关题目

例题

3302. 表达式求值（栈的应用）😭😭😭😭😭

https://www.acwing.com/activity/content/problem/content/3648/
在这里插入图片描述

import java.util.*;public class Main {// 存储数字的栈static Deque<Integer> numStk = new LinkedList<>();// 存储运算符号的栈static Deque<Character> opStk = new LinkedList<>();public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s = scanner.next();// 各个运算符的优先级字典Map<Character, Integer> pr = Map.of('+', 1, '-', 1, '*', 2, '/', 2);for (int i = 0; i < s.length(); ++i) {char ch = s.charAt(i);// 如果是数字，直接放入栈里if (Character.isDigit(ch)) {int x = 0, j = i;while (j < s.length() && Character.isDigit(s.charAt(j))) {x = x * 10 + (s.charAt(j) - '0');++j;}i = j - 1;numStk.push(x);} else if (ch == '(') opStk.push(ch);   // 左括号直接放入栈里else if (ch == ')') {                   // 出现右括号，一直计算到出现左括号while (opStk.peek() != '(') eval();opStk.pop();    // 把'('弹出来} else {            // 是运算符号，检查和上个运算符号之间的优先级关系如何，先算优先级大的while (!opStk.isEmpty() && opStk.peek() != '(' && pr.get(opStk.peek()) >= pr.get(ch)) eval();opStk.push(ch);}}while (!opStk.isEmpty()) eval();    // 把剩下的运算符都计算了System.out.println(numStk.peek());}static void eval() {// 取出两个数字和一个运算符进行运算int b = numStk.pop(), a = numStk.pop();char ch = opStk.pop();int x;if (ch == '+') x = a + b;else if (ch == '-') x = a - b;else if (ch == '*') x = a * b;else x = a / b;numStk.push(x);}
}

这题思路有难度，代码也很长。

使用栈来解决这个问题。

遇到数字时，直接将数字放入栈中。
遇到 ( 时，也直接放入栈中。
遇到 ) 时，进行计算知道栈顶是（。
遇到运算符时，和当前在栈顶的运算符进行比较，先计算优先级高的运算符。

830. 单调栈

https://www.acwing.com/activity/content/problem/content/867/

在这里插入图片描述

知识点

单调栈可以用来求取数组中每一个元素左右两边第一个比它大或者第一个比它小的位置在哪里。

解法

为了求每个数字左边第一个比它小的数字，需要使用一个单调栈。

这个单调栈从栈底到栈顶是单调递减的。

当枚举到一个元素时，从栈顶开始检查，如果栈顶的元素比当前元素小，那就找到了当前元素左边第一个更小的元素；
如果栈顶的元素 >= 当前的元素，那么就将其弹出栈。

如果栈是空的，说明左侧没有比当前元素更小的元素了。

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < n; ++i) {int x = scanner.nextInt();while (!stk.isEmpty() && x <= stk.peek()) stk.pop();if (!stk.isEmpty()) System.out.print(stk.peek() + " ");else System.out.print("-1 ");stk.push(x);}}
}

154. 滑动窗口（单调队列）

https://www.acwing.com/activity/content/problem/content/868/
在这里插入图片描述

知识点

单调队列常常用来维护一个窗口中当前的最大值或者最小值。

注意单调队列要使用 双端队列 来实现。

解法

使用两个双端队列分别维护当前窗口中的最大值和最小值。

和单调栈类似，每次枚举到一个新的元素时，将该元素一直与队列中的最后一个元素相比较，保持队列的单调性。

每个窗口的最大值和最小值就是队列队首的元素。

记得要及时移除窗口之外的元素。

import java.io.BufferedInputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {Scanner sin = new Scanner(new BufferedInputStream(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));int n = sin.nextInt(), k = sin.nextInt();int[] a = new int[n], max = new int[n - k + 1], min = new int[n - k + 1];Deque<Integer> dqMax = new ArrayDeque<>(), dqMin = new ArrayDeque<>();for (int i = 0; i < n; ++i) {a[i] = sin.nextInt();while (!dqMax.isEmpty() && a[dqMax.peekLast()] <= a[i]) dqMax.pollLast();dqMax.offerLast(i);while (dqMax.peekFirst() + k <= i) dqMax.pollFirst();while (!dqMin.isEmpty() && a[dqMin.peekLast()] >= a[i]) dqMin.pollLast();dqMin.offerLast(i);while (dqMin.peekFirst() + k <= i) dqMin.pollFirst();if (i >= k - 1) {max[i - k + 1] = a[dqMax.peekFirst()];min[i - k + 1] = a[dqMin.peekFirst()];}}for (int i = 0; i < n - k + 1; ++i) bw.write(min[i] + " ");bw.write("\n");for (int i = 0; i < n - k + 1; ++i) bw.write(max[i] + " ");bw.flush();sin.close();bw.close();}
}