Day11 ＞＞ 150、逆波兰表达式求值 + 239、滑动窗口最大值 + 347、前K个高频元素
代码随想录-栈
150、逆波兰表达式求值
刚开始看到题目的时候有点懵，不太了解逆波兰表达式，其实就是后缀表达式，是计算机的思考运行模式。这道题很适合用栈来解决，思路：
- 定义一个 Int 型的栈
- 然后去遍历字符串：
- 遍历到数值时，就压入栈中
- 遍历到运算符时，就取栈顶的两个元素进行运算，并将结果压入栈中
- 字符串遍历完成后，取出栈中的元素返回即可
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> st = new Stack(); for (int i = 0; i < tokens.length; i++) { if ("+".equals(tokens[i]) || "-".equals(tokens[i]) || "*".equals(tokens[i]) || "/".equals(tokens[i])) { int number1 = st.pop(); int number2 = st.pop(); if ("+".equals(tokens[i])) st.push(number1 + number2); if ("-".equals(tokens[i])) st.push(number2 - number1); if ("*".equals(tokens[i])) st.push(number2 * number1); if ("/".equals(tokens[i])) st.push(number2 / number1); } else { st.push(Integer.valueOf(tokens[i])); } } return st.pop(); } }做这道题目时，出了两种错误
- 对 Java 中字符类型的判断函数使用错误，写成了 "+" == tokens[i] ，这是错误的，因为 == 比较的是内存地址，也就是引用是否相同，而本题是需要比较字符串的内容，需要使用equals()
- 在取栈顶元素时，误用了栈的操作函数，写成了 int number1 = st.top() ，这里是使用了视频中卡哥讲的c++取栈顶元素的API，但是在Java中，应该使用 .pop() 函数
int number1 = st.pop(); // 弹出并返回栈顶元素 // 或 int number1 = st.peek(); // 仅返回栈顶元素（不弹出）另外，在探索学习的过程中，AI还指出了当前代码太low了，存在两个可以优化的点：
- for循环中的索引遍历，可以使用for-each代替
- if-else 结构可以使用 switch 进行优化，使代码可读性更强，更简洁
优化完虽然代码行数变多了，但是执行效率提高了很多
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> st = new Stack(); for (String token : tokens) { switch (token) { case "+" : st.push(st.pop() + st.pop()); break; case "*" : st.push(st.pop() * st.pop()); break; case "-" : int number1 = st.pop(); int number2 = st.pop(); st.push(number2 - number1); break; case "/" : int div1 = st.pop(); int div2 = st.pop(); st.push(div2 / div1); break; default : st.push(Integer.parseInt(token)); } } return st.pop(); } }239、滑动窗口最大值
这道题看起来感觉思路挺清晰的，无非就是每滑动一次找出窗口范围内的最大值，但实现起来真是复杂，看了视频讲解，独立写的时候还卡住好多次，思路：
- 定义一个Deque，用于存储数组的索引，以此来定位滑动窗口的最大值（这里为什么存储下标，不直接存储数组的值？是因为存储下标，便于根据下标判断滑动窗口的有效位置）
- 定义一个整型数组，长度为 n-k+1，用于存储在滑动窗口中找到的最大值（这里为什么长度是 n-k+1，因为窗口在数组上移动时，有效位置范围是[0, n-k]，所以共 n-k+1 个位置）
- 定义一个指针，从0开始，往数组中增加元素
- 开始遍历数组
- 遍历数组时，将满足条件的数值对应的下标存放入Deque中
- 由于题目要求在窗口范围内查找最大值，所以当窗口往后滑动的过程中，需要移除超出窗口内有效位置的下标，即 Deque.peek() < i-k+1
- 此外，为便于在窗口滑动的过程中获取最大值，将队列维护成单调队列，保持队列头部元素为最大值，如果即将加入的元素小于当前队列中已有元素，那正常加入队列，如果即将加入的元素大于当前队列中已有元素，那么就从队列尾部弹出当前队列的元素，直到队列中的元素大于即将加入的元素（因为要找最大值，如果加入的元素比之前的大，那么之前的元素就没必要再比较了，肯定不会是当前滑动窗口的最大值）
- 当 i 遍历到满足一个有效滑动窗口的位置时，就可以找出当前窗口的最大值了；由于是单调队列，所以后面获取最大值时，只需将队列头部元素对应下标的数组元素放入结果数组中即可
- 遍历完整个数组后，返回整型数组即可
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { ArrayDeque<Integer> deque = new ArrayDeque(); int n = nums.length; int[] result = new int[n - k + 1]; int index = 0; for (int i = 0; i < n; i++) { while (!deque.isEmpty() && deque.peek() < i - k + 1) { deque.poll(); } while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) { deque.pollLast(); } deque.offer(i); if (i >= k - 1) { result[index++] = nums[deque.peek()]; } } return result; } }347、前K个高频元素
拿到题目想到了用map结构来记录每个元素出现的频次，然后再根据map中，最大的前K个value对应的key，从而得出结果。但根据value排序取对应的key好像挺复杂的，不知道怎么实现，去看了讲解后，才意识到需要用优先级队列这个数据结构，思路：
- 定义一个HashMap，用于存放元素、及其出现的频次
- 遍历数组，将元素值记为key，出现的频次记为value，存入map中
- 定义一个优先级队列，这里以小顶堆的方式定义该队列
- 遍历map：
- 如果当前队列的长度还没有达到 k，则继续往队列中增加value
- 如果当前队列的长度已经达到 k，则比较将要加入的 value 与当前队列头部的value，也就是堆顶的value，如果即将要加入的元素更大，则把堆顶弹出，在后面加入新元素
- 遍历完map，构建完小顶堆后，将堆元素逐个弹出，并存放在数组中即可
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[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[] result = new int[k]; for (int i = k - 1; i >= 0; i--) { result[i] = pq.poll()[0]; } return result; } }