代码随想录算法训练营第11天
150.逆波兰表达式求值
题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）
文档/视频链接：代码随想录 (programmercarl.com)
第一想法
碰到数字就先压入栈中，碰到符号取出两个数运算压入栈中。最终取出栈空即可。
代码随想录
将字符串转换为数字可以用Integer.valueOf(s)代替，不用自己写函数.
"+".equals（s）:正确写法应该是这样的。
可以用增强for循环
代码
class Solution1 {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String s: tokens){if("+".equals(s))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 a =stack.pop();int b =stack.pop();stack.push(b/a);}else{stack.push(Integer.valueOf(s));}}return stack.pop();}
}239.滑动窗口最大值
题目链接：239. 滑动窗口最大值 - 力扣（LeetCode）
视频链接：代码随想录 (programmercarl.com)
第一想法
我的实力不允许我挑战困难的题啊。
最大值结果数组大小为nums.leng()-k+1
每轮暴力遍历么？
代码随想录
定义单调队列，放进去窗口里的元素，随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面最大值是什么。最大值是队列第一个元素
pop()规则：若窗口要移除的元素等于单调队列出口元素，则队列弹出元素，否则不做任何操作
移除元素等于出口元素的等价条件不是队列元素已满（queue.size()==k）
push（）规则：如果push元素大于入口处元素，那么就将队列入口处的元素弹出。这里的弹出不是将队列所有元素弹出
//保证队列元素单调递减//比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2基本数据结构：双端队列ArrayDeque，LinkedList
代码
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {MyQueue myQueue = new MyQueue();int[] results = new int[nums.length-k+1];int j = 0;for (int i = 0; i < k; i++) {myQueue.push(nums[i]);}results[j++]=myQueue.getMaxValue();for (int i = k; i < nums.length; i++) {myQueue.pop(nums[i-k]);myQueue.push(nums[i]);results[j++] = myQueue.getMaxValue();}return results;}
}
class MyQueue{Deque<Integer> deque = new LinkedList<>();public void pop(int val){if(!deque.isEmpty()&&val == deque.getFirst()){deque.pollFirst();}}public void push(int val){while (!deque.isEmpty()&&deque.getLast()<val){deque.pollLast();}deque.offer(val);}public int getMaxValue(){return deque.getFirst();}
}347.前K个高频元素
题目链接：347. 前 K 个高频元素 - 力扣（LeetCode）
文档/视频链接：代码随想录 (programmercarl.com)
第一想法
想到LeetCode27题，可以用map集合统计频率，键为数组元素，值为频次。然后按照值全部排序返回前k个较大者。使用Java8 Stream API对Map按键或值进行排序 - 字母哥博客 - 博客园 (cnblogs.com)
代码随想录
此题只用维护k个有序的序列就可以了，所以使用优先级队列是最优的。选用小顶堆。若选用大顶堆，每次push元素，维护队列时，实际上会把最大的元素弹出去，最后留下的是前k个最小的元素。
难点
初始化优先级队列
构造小顶堆
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> (pair1[1] - pair2[1]));这行代码创建了一个优先队列（PriorityQueue），其中存储的元素是 int 数组。这里使用了一个 lambda 表达式作为参数，来定义优先队列中元素的比较规则。
具体来说，`(pair1, pair2) -> (pair1[1] - pair2[1])` 这个 lambda 表达式定义了比较器，表示如果 `pair1` 的第二个元素小于 `pair2` 的第二个元素，则 `pair1` 比 `pair2`“优先级”高，应该在队列中排在前面。这样初始化的 PriorityQueue 就会按照每个元素的第二个元素的大小升序排列，即按照频率从小到大排列。
在这段代码中，用于优先队列的元素是 int 数组，数组中第一个元素存储数字，第二个元素存储该数字在数组中出现的频率。通过定义这样的比较器，可以确保优先队列中的元素按照频率从小到大有序排列，方便根据频率选择前 k 个高频元素。
构造大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
这个 lambda 表达式 (a, b) -> b - a 会对元素进行逆序比较，从而构造一个大顶堆。
代码
class Solution {public int[] topKFrequent(int[] nums, int k) {// 使用 HashMap 统计每个数字出现的频率Map<Integer,Integer> map = new HashMap<>();for(int num:nums){map.put(num,map.getOrDefault(num,0)+1);}// 使用优先队列（最小堆）来存储频率最高的 k 个元素，按照频率排序// 优先队列中存储 int 数组，数组第一个元素是数字，第二个元素是频率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()});}}}// 构建结果数组，存储前 k 个高频元素int[] ans = new int[k];for(int i = k - 1;i>=0;i--){ans[i] = pq.poll()[0];}return ans;}
}