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

150. 逆波兰表达式求值
题目链接：150. 逆波兰表达式求值
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰逆波兰表达式求值
日期：2024-09-07

想法：用栈解决，遇到运算符取前两个数字计算（表达式总是成立的，不用做额外的判定）
Java代码如下：

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new ArrayDeque<>();
        for(String s : tokens){
            if("+".equals(s)){
                deque.push(deque.pop() + deque.pop());
            }else if("-".equals(s)){
                deque.push(-deque.pop() + deque.pop());
            }else if("*".equals(s)){
                deque.push(deque.pop() * deque.pop());
            }else if("/".equals(s)){
                int temp1 = deque.pop();
                int temp2 = deque.pop();
                deque.push(temp2 / temp1);
            }else{
                deque.push(Integer.valueOf(s));
            }
        } 
        return deque.pop();
    }
}

总结：判定得用equals，-，/得特殊处理。

239. 滑动窗口最大值
题目链接：239. 滑动窗口最大值
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰滑动窗口最大值
日期：2024-09-07

想法：想的是从头开始，遍历数组找到每k个中最大值，只能算暴力解法，时间复杂度O（n + k）。但使用单调队列（单调递减）能更方便
Java代码如下：

class MyQueue {
    Deque<Integer> deque = new LinkedList<>();

    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }

    void 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 n = 0;
        MyQueue myQueue = new MyQueue();
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        res[n++] = myQueue.peek();
        for (int i = k; i < nums.length; i++) {
            myQueue.poll(nums[i - k]);
            myQueue.add(nums[i]);
            res[n++] = myQueue.peek();
        }
        return res;
    }
}

总结：总的来说就是要将队列中的最前的值设置为最大，入队列时如果队列里有数，一直让要入队列的数与队尾比大，维护整个队列单减，弹出时就要看看队首的数是不是要删的数，有可能你弹出的位置在之前加入时就已经被删了。

347.前 K 个高频元素
题目链接：347.前 K 个高频元素
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰347.前 K 个高频元素
日期：2024-09-07

想法：用小顶堆，统计最大前k个元素，每次将最小的元素弹出，最后小顶堆里积累的就是前k个最大元素
Java代码如下：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums)
            map.put(n, map.getOrDefault(n, 0) + 1);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (int key : map.keySet()) {
            pq.offer(key);
            if (pq.size() > k) 
                pq.poll();
        }
        int[] res = new int[k];
        int i = 0;
        while (!pq.isEmpty())
            res[i++] = pq.poll();
        return res;
    }
}