代码随想录算法训练营第11天 | 150. 逆波兰表达式求值、239. 滑动窗口最大值、347.前 K 个高频元素

目录

单调队列

1. 单调队列的定义

2. 单调队列的操作

3. 单调队列的应用

4. 单调队列的优势

5. 实现细节

150.逆波兰表达式求值

1.解题思路

2.我的实现

实现遇到的问题

对于break的使用

将字符转换成int

代码

代码中的错误

3.标准实现

区别

4.题目总结

239. 滑动窗口最大值

1.解题思路

2.我的实现

实现遇到的问题

代码

3.标准实现

4.题目总结

347.前 K 个高频元素（！！！）

1.解题思路

2.我的实现

实现遇到的问题

代码

3.标准代码

4.题目总结

单调队列

单调队列（Monotonic Queue）是一种特殊的队列结构，通常用于在滑动窗口、最大最小值等问题中实现高效的查询操作。以下是单调队列的基本概念及其在相关问题中的应用总结：

1. 单调队列的定义

• 单调递增队列：队列中的元素按值递增排序。当我们向队列中添加一个新元素时，所有比它大的元素都会被移除，以保持队列的单调性。及最后一个元素最大
• 单调递减队列：队列中的元素按值递减排序。当我们向队列中添加一个新元素时，所有比它小的元素都会被移除，以保持队列的单调性。及最后一个元素最小

2. 单调队列的操作

• 入队 (enqueue)：插入新元素时，根据单调性移除不符合条件的元素。
• 出队 (dequeue)：根据需要从队列头部移除元素，通常与滑动窗口的左边界移动有关。
• 保持单调性：通过在入队时移除不符合单调性的元素，队列始终保持单调性。

3. 单调队列的应用

• 滑动窗口中的最大/最小值问题：在给定数组中找到每个长度为 k 的子数组的最大或最小值。单调队列可以在 O(n) 时间内完成此操作，其中 n 是数组的长度。
• 动态维护区间最值：单调队列能够高效地维护区间中的最大值或最小值，适用于需要频繁更新区间的场景。

4. 单调队列的优势

• 高效性：通过维护队列的单调性，可以在常数时间内获得当前区间的最值，并且只需线性时间复杂度遍历整个数组。
• 空间效率：队列的空间复杂度通常为 O(k)，其中 k 是滑动窗口的大小。

5. 实现细节

• 数据结构：可以使用双端队列（Deque）来实现单调队列，双端队列支持在队列两端进行高效的插入和删除操作。
• 入队操作：插入新元素时，从队尾逐一比较并移除不符合单调性的元素，然后将新元素插入队尾。
• 出队操作：在滑动窗口问题中，当窗口左边界向右移动时，如果当前最大或最小值已不在窗口范围内，则从队列头部移除它。

150.逆波兰表达式求值

题目链接：逆波兰表达式求值

1.解题思路

把元素放入栈中，遇到操作符后，将最后两个元素拿出来操作，最后一个作为右操作符，前一个作为左操作符，然后再把操作结果放入进去。整个后缀表达式的结果就是栈中最后一个元素。

2.我的实现

实现遇到的问题

对于break的使用

1.在switch语句中：break只终止当前case的执行，跳出switch语句。

2.在循环结构中：break终止整个循环。

将字符转换成int

Integer.parseInt(tokens[i]) 的作用就是将位于 tokens 数组第 i 个位置上的字符串转换为整数。

代码

public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();int num1,num2;for (int i = 0; i < tokens.length; i++) {switch (tokens[i]) {case "+":num2=stack.pop();num1=stack.pop();stack.push(num1+num2);break;case "-":num2=stack.pop();num1=stack.pop();stack.push(num1-num2);break;case "*":num2=stack.pop();num1=stack.pop();stack.push(num1*num2);break;case "/":num2=stack.pop();num1=stack.pop();stack.push(num1/num2);break;default:stack.push(Integer.parseInt(tokens[i]));//将字符转换成int类型break;}}return stack.peek();}

代码中的错误

3.标准实现

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList();for (String s : tokens) {if ("+".equals(s)) {        // leetcode 内置jdk的问题，不能使用==判断字符串是否相等stack.push(stack.pop() + stack.pop());      // 注意 - 和/ 需要特殊处理} else if ("-".equals(s)) {stack.push(-stack.pop() + stack.pop());} else if ("*".equals(s)) {stack.push(stack.pop() * stack.pop());} else if ("/".equals(s)) {int temp1 = stack.pop();int temp2 = stack.pop();stack.push(temp2 / temp1);} else {stack.push(Integer.valueOf(s));}}return stack.pop();}
}

区别

4.题目总结

栈

• 定义：堆栈是一种后进先出 (LIFO) 的数据结构，适合处理逆波兰表示法表达式的计算。
• 操作：在遇到操作数时，将其压入栈中；在遇到操作符时，从栈中弹出相应数量的操作数，进行计算后将结果再压入栈中。
• 用途：在逆波兰表达式计算中，堆栈用于存储操作数和中间计算结果。

239. 滑动窗口最大值

题目链接：滑动窗口最大值

1.解题思路

用一个双端队列，每移动一个元素就pop最后一个，push最新的一个，然后再获得最大值。

pop保持队列出口出是最大的一个元素，当进入的比前面大时，就把前面的pop出去

小的话就可以放进来，因为我们维护的是出口处的元素。

相当于这个队列中只储存两个值一个是最大值储存到第一位，一个是最后一个为最大值，储存在第二位，相等时接着后面储存

2.我的实现

实现遇到的问题

1.ArrayDeque 和 LinkedList用哪个实现Deque更好：

ArrayDeque 是滑动窗口问题中实现双端队列的最佳选择。它能够提供高效的双端操作，确保滑动窗口在处理过程中能够快速、稳定地完成元素的插入、删除和查询。

2.注意避免重复判断，重复加入会引起错误，学会用else。

代码

public static int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> deque = new ArrayDeque<>();int[] result = new int[nums.length - k+1];for (int i = 0; i < nums.length; i++) {if (deque.isEmpty()){deque.addLast(nums[i]);}else if (nums[i] > deque.getFirst()) {//如果大于了最前面的数// 那所有数都要移走while (!deque.isEmpty()) {deque.pollLast();}deque.addLast(nums[i]);}else {while (deque.peekLast()<nums[i]){deque.pollLast();}deque.addLast(nums[i]);int a=nums[i];}if (i >= k - 1) {result[i - k + 1] = deque.getFirst();//以窗口最后一个数为i,第一个数为i-k+1//当最大数等于窗口第一个数时，意味着要移除if (deque.getFirst() == nums[i - k + 1]) {deque.pollFirst();}}}return result;}

3.标准实现

//解法一
//自定义数组
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;}
}//解法二
//利用双端队列手动实现单调队列
/*** 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可* 单调队列类似 （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;}
}

4.题目总结

解题思路里

public int[] topKFrequent2(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}//在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序if (pq.size() < k) { //小顶堆元素个数小于k个时直接加pq.add(new int[]{entry.getKey(), entry.getValue()});} else {if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了pq.add(new int[]{entry.getKey(), entry.getValue()});}}}int[] ans = new int[k];for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多ans[i] = pq.poll()[0];}return ans;}

public int[] topKFrequent2(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}//在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序if (pq.size() < k) { //小顶堆元素个数小于k个时直接加pq.add(new int[]{entry.getKey(), entry.getValue()});} else {if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了pq.add(new int[]{entry.getKey(), entry.getValue()});}}}int[] ans = new int[k];for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多ans[i] = pq.poll()[0];}return ans;}