代码随想录算法训练营第11天

150.逆波兰表达式求值

题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

文档/视频链接：代码随想录 (programmercarl.com)

 第一想法

碰到数字就先压入栈中，碰到符号取出两个数运算压入栈中。最终取出栈空即可。

代码随想录

将字符串转换为数字可以用Integer.valueOf(s)代替，不用自己写函数.

"+".equals（s）:正确写法应该是这样的。

可以用增强for循环

代码

class Solution1 {
    public int evalRPN(String[] tokens) {
        Stack 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 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()
            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 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 entry : map.entrySet()) {
            if(pq.size()
                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;
    }
}