前言
代码随想录系列已经两天没更了，是我懒了，今天继续
今天任务：
我之前有专门写过栈方面的文章，可以作为前置文章进行学习，对栈和队列不是很熟悉的小伙伴可以看一下# 你有用过 java中的栈和队列吗？怎么用栈来实现队列呢
150. 逆波兰表达式求值
题目描述
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例
输入： tokens = ["2","1","+","3","*"] 输出： 9 解释： 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 复制代码
输入： tokens = ["4","13","5","/","+"] 输出： 6 解释： 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6 复制代码
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 复制代码
思路分析
根据题目和示例可以看出来每次进行运算的都是 运算符前两个数字，那么我们就可以遍历 tokens并判断是不是 +-*/， 如果是运算符的话就直接进行运算，如果不是的话就放入栈中
代码展示
public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (int i = 0; i < tokens.length; i++) { String token = tokens[i]; int m = 0; if (token.equals("+")){ m = stack.pop() + stack.pop(); }else if (token.equals("-")){ m = -stack.pop() + stack.pop(); }else if (token.equals("*")){ m = stack.pop() * stack.pop(); }else if (token.equals("/")){ int n = stack.pop(); m = stack.pop() / n; }else{ m = Integer.valueOf(token); } stack.push(m); } return stack.pop(); } 复制代码
提交结果
这里需要注意的是在 LeetCode内置的 jdk不支持字符串 ==，只能使用 String.equals()方法
239. 滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 复制代码
示例 2：
输入：nums = [1], k = 1 输出：[1] 复制代码
提示：
1 <= nums.length <= 105 -104 <= nums[i] <= 104 1 <= k <= nums.length 复制代码
思路分析
本题我采用单调队列来做
使用队列来记录元素下标，依此判断元素长度是否超过了三，如果超过三则弹出
因为是获取最大值，所以此队列应该是非递增的，判断当前元素是否大于队列的最后一个元素，若大于则抛出最后一个元素
最后将当前元素下标放入队列
代码展示
public static int[] maxSlidingWindow(int[] nums, int k) { int length = nums.length - k + 1; int[] result = new int[length]; ArrayDeque<Integer> queue = new ArrayDeque<>(); int num = 0; for (int i = 0; i < nums.length; i++) { while(!queue.isEmpty() && queue.peek() < i - k + 1){ queue.poll(); } while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){ queue.pollLast(); } queue.offer(i); if (i >= k - 1){ result[num++] = nums[queue.peek()]; } } return result; } 复制代码
提交结果
总结
这道题还是很难的， 我也是思考之后看了题解才做出来，通过以前的代码提交记录也可以看出来我在这道题上也花费了很多时间
347. 前 K 个高频元素
对优先级队列不了解的小伙伴建议先看我之前写的文章 # 从构造方法到实战练习优先级队列 PriorityQueue
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 复制代码
示例 2:
输入: nums = [1], k = 1 输出: [1] 复制代码
提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
思路分析
判断前 k个高频元素，那肯定是遍历保存每个元素出现的次数，关于获取到队列元素的出现个数之后， 遍历 map，将元素放入到优先级队列中 PriorityQueue，然后遍历 k个元素
代码展示
public int[] topKFrequent(int[] nums, int k) { int[] result = new int[k]; // 优先级队列元素 Map<Integer,Integer> map = new HashMap<>(); // 遍历 nums获取元素及其出现次数 for (int i = 0; i < nums.length; i++) { int num = nums[i]; map.put(num, map.getOrDefault(num, 0 ) + 1); } Set<Map.Entry<Integer, Integer>> entries = map.entrySet(); PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue()); for (Map.Entry<Integer, Integer> entry : entries) { queue.add(entry); } for (int i = 0; i < k; i++) { result[i] = queue.poll().getKey(); } return result; } 复制代码
提交结果
