代码随想录第十一天|栈与队列part02--150.逆波兰表达式求值、239.滑动窗口最大值、347.前k个高频元素、栈与队列总结篇

150.逆波兰表达式求值（150.逆波兰表达式求值）

题目分析：

计算逆波兰表达式（后缀表达式：左右中）的值，算符仅包含四则运算，操作数为一个整数或另一个表达式，整数除法向零截断（向下取整），无除零运算，答案及中间结果不超过32位，即使用整型int即可。

解题重点：

后缀表达式的每一个表达式中：读入1个算符即就近向前匹配2个操作数，所得结果作为下一表达式的操作数之一。考虑使用栈结构解决该问题。

解题思路：

用Deque实现一个泛型为Integer的栈s。

遍历从tokens读入元素，若为整数则push入栈，若为算符则先pop出栈2个操作数，按出栈顺序的第一个操作数为右操作数，第二个操作数为左操作数，再用该算符对这两个操作数做运算，最后将所得结果push入栈。

直至遍历tokens并操作完全，栈中所得结果即为最终结果。

总结：

（摘录自carl哥）

我们习惯看到的表达式都是中缀表达式，因为符合我们的习惯，但是中缀表达式对于计算机来说就不是很友好了。

例如：4 + 13 / 5，这就是中缀表达式，计算机从左到右去扫描的话，扫到13，还要判断13后面是什么运算符，还要比较一下优先级，然后13还和后面的5做运算，做完运算之后，还要向前回退到 4 的位置，继续做加法，你说麻不麻烦！

那么将中缀表达式，转化为后缀表达式之后：["4", "13", "5", "/", "+"] ，就不一样了，计算机可以利用栈来顺序处理，不需要考虑优先级了。也不用回退了， 所以后缀表达式对计算机来说是非常友好的。

可以说本题不仅仅是一道好题，也展现出计算机的思考方式。

补充：在1970年代和1980年代，惠普在其所有台式和手持式计算器中都使用了RPN（后缀表达式），直到2020年代仍在某些模型中使用了RPN。

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> s = new ArrayDeque<>();int left = 0;int right = 0;for(String token : tokens){switch (token) {case "+":right = s.pop();left = s.pop();s.push(left + right);break;case "-":right = s.pop();left = s.pop();s.push(left - right);break;case "*":right = s.pop();left = s.pop();s.push(left * right);break;case "/":right = s.pop();left = s.pop();s.push(left / right);break;default:s.push(Integer.parseInt(token));break;}}return s.pop();}
}

239.滑动窗口最大值（239.滑动窗口最大值）

题目分析：

给定整数数组nums，有一个长为k的滑动窗口从数组的最左侧移动到最右侧，滑动窗口每次输出当前窗口的k个数字中的最大值，然后向右移动一位。

题目重点：

根据提示，采用队列来实现。由于滑动窗口从左到右滑动，每次从窗口左端移出一个数，从窗口右端移进一个数，符合先进先出的单调队列。队列轻松实现了窗口的增删。

解题思路：

初始化滑动窗口的左边界指针cur为0（从左到右遍历数组直到cur+k<nums.length不成立为止），初始化max为0，初始化整型数组result的大小为nums.length-k+1。

初始化滑动窗口队列q，依次将cur,cur+1,...,cur+k-1添入队列并记录其最大值为max，输出max。

滑动窗口每次右移一位，记录移出的数为out，记录移进的数为in

若in>=max，则置max为in
否则in<max

- 若out!=max，则max不变
- 否则

- - 初始化count=k，max=in
  - 遍历队列寻找最大值（注意队列进出）

输出max

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> q = new ArrayDeque<>();int cur = 0;int max = 0;int[] result = new int[nums.length-k+1]; //共得nums.length-k+1个maxfor(int i = 0;i < k;i++){int temp = nums[cur+i];if (temp > max)max = temp;q.offer(temp);}result[cur] = max;while(cur+k < nums.length){int out = q.poll(); // 从队头移出int in = nums[cur+k]; //cur+k自带多1位，从而省略了初始的cur右移及其边界判断q.offer(in); // 从队尾移入/*寻找最大值 */if (in >= max)max = in;else{if (out != max)max = max;else{int count = k;max = in;while(count > 0){ //遍历队列寻找最大值int temp = q.poll();if (temp > max)max = temp;q.offer(temp);count--;}}}result[++cur] = max; //由于初始的cur+k自带多一位，所以此处用++cur先移进，后添加}return result;}
}

思路改进：

由于原解法的最坏情况是O(n*k)，需要改进。

重新审题，发现只需考虑滑动窗口中的最大值，则考虑利用具有单调性的单调队列来实现。

审题思路：

由于队列只需维护窗口里的最大值，而非维护窗口中的所有元素，并保证该队列是单调递减的（利用peek从出口读出最大值），因此该队列应为单调队列。

该单调队列应满足如下条件：

随时可以获取队列中的最大值，则应为单调递减队列，使用peek方法获取队头
窗口移动时当且仅当队列的出口元素为窗口的移出元素时，将该出口元素poll出
窗口移动时当且仅当队列的入口元素大于窗口的移入元素时，将该移入元素add入（实现单调递减队列）

//解法一
//自定义数组
class MyQueue {Deque<Integer> deque = new LinkedList<>();//弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出//同时判断队列当前是否为空void poll(int val) {if (!deque.isEmpty() && val == deque.peek()) {deque.poll();}}//添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出//保证队列元素单调递减//比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2void add(int val) {while (!deque.isEmpty() && val > deque.getLast()) {deque.removeLast();}deque.add(val);}//队列队顶元素始终为最大值int peek() {return deque.peek();}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length == 1) {return nums;}int len = nums.length - k + 1;//存放结果元素的数组int[] res = new int[len];int num = 0;//自定义队列MyQueue myQueue = new MyQueue();//先将前k的元素放入队列for (int i = 0; i < k; i++) {myQueue.add(nums[i]);}res[num++] = myQueue.peek();for (int i = k; i < nums.length; i++) {//滑动窗口移除最前面的元素，移除是判断该元素是否放入队列myQueue.poll(nums[i - k]);//滑动窗口加入最后面的元素myQueue.add(nums[i]);//记录对应的最大值res[num++] = myQueue.peek();}return res;}
}

解法2：由于滑动窗口在数组上从左至右移动，欲利用数组下标判断队列中的出口元素是否需要移出，只需将最大值对应的数组下标存入队列即可，维护对象从最大值转变为最大值的下标。

//解法二
//利用双端队列手动实现单调队列
/*** 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可* 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)*/
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {ArrayDeque<Integer> deque = new ArrayDeque<>();int n = nums.length;int[] res = new int[n - k + 1];int idx = 0;for(int i = 0; i < n; i++) {// 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点// 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出while(!deque.isEmpty() && deque.peek() < i - k + 1){deque.poll();}// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();}deque.offer(i);// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了if(i >= k - 1){res[idx++] = nums[deque.peek()];}}return res;}
}

347.前k个高频元素（347.前k个高频元素）

题目分析：

返回整数数组nums中出现频率前k高的元素，返回顺序任意。

分解任务如下：

统计元素出现频率
按频率排序
找出前k个高频元素

既要记录元素，同时记录其出现频率，通过map来进行统计。

此时如果有一个能够自动排序的容器就好了，在这里我们考虑采用优先级队列进行实现。

解题重点与思路：

优先级队列是披着队列外衣（仅入队出队跟队列相关）的大/小顶堆。

大（小）顶堆是一个完全二叉树，树中的每个结点的值都不小于（不大于）其左右孩子的值。

本题考虑采用小顶堆，理由如下：

由于只需维护k个最大的元素，而优先队列pop从堆顶pop出，若用大顶堆则相当于每次弹出都是弹出最大的元素。
只需维护k个最大的元素，每次弹出当前最小的元素即可，最终留在小顶堆中的就是频率前k大的数。

使用小顶堆，扫描map的过程中，每次只需与堆顶元素比较，若堆顶元素较小则将其弹出，并压入新的元素（自动维护顺序），最终小顶堆里积累的就是前k个最大元素。

总结反思：

学习了优先级队列的两种实现方式，了解了小顶堆和大顶堆的区别，手敲复盘了代码的实现。

注意点：

map.getOrDefault(num,0)方法的使用
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);中lamda表达式的使用
以Map.Entry<Integer, Integer> entry为例的map中的entry相关的使用
以new int[]{entry.getKey(), entry.getValue()为例的元组的构建

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>(); //key为数组元素，val为对应的频率for(int num : nums) {map.put(num, map.getOrDefault(num,0) + 1);}// 优先级队列，为了避免复杂 api 操作，pq 存储数组// lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从小到大，o2 - o1 反之PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if (pq.size() < k) {pq.add(new int[]{entry.getKey(), entry.getValue()});} else {if (entry.getValue() > pq.peek()[1]) {pq.poll();pq.add(new int[]{entry.getKey(), entry.getValue()});}}}int[] res = new int[k];for (int i = 0; i<k; i++){res[i]=pq.poll()[0];}return res;}
}

栈与队列总结篇

栈与队列的理论基础

由该章节我们了解到了一个重要的问题：

栈里面的元素在内存中是连续分布的么？

答案为否，理由如下：

栈是容量适配器，底层容器可以使用不同的容器，因此栈内数据在内存中不一定是连续分布的（ArrayList实现Deque接口是连续的，LinkedList实现Deque接口是不连续的）。

栈经典题目

栈在系统中的应用

编译原理中，编译器在词法分析过程处理各种括号的正确匹配问题就是用栈实现的
linux系统中，cd a/b/c/../../命令最后进入a目录就是利用栈实现的（先进后出）

- 首先，a被推入栈中，当前目录变为a。
- 接着，b被推入栈中，当前目录变为a/b。
- 然后，c被推入栈中，当前目录变为a/b/c。
- 遇到../时，系统会从栈中弹出（也就是移除）最顶部的路径段，因为../表示返回上一级目录。在这个例子中，c被弹出，当前目录回到a/b。
- 再次遇到../，b被弹出，当前目录回到a。
- 最终栈中只剩下a，系统将当前目录改变为a。