Day10(栈与队列) | 150. 逆波兰表达式求值 239. 滑动窗口最大值 347.前 K 个高频元素

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

后缀转中缀,使用栈即可

代码如下:

@Test
    public void test01() {
        String[] str = new String[]{"2", "1", "+", "3", "*"};
        System.out.println("逆波兰表达式的结果是:" + evalRPN(str));
    }

    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (String str : tokens) {
            switch (str) {
                case "+" -> stack.push(stack.pop() + stack.pop());
                case "-" -> stack.push(-stack.pop() + stack.pop());
                case "*" -> stack.push(stack.pop() * stack.pop());
                case "/" -> {
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    stack.push(num2 / num1);
                }
                default -> stack.push(Integer.valueOf(str));
            }
        }
        return stack.pop();
    }

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]

思路 : 这是我第一次接触到单调队列,这次用到的辅助数据结构是递减单调队列.

遍历数组nums,在将i位置放入单调队列前,需要判断这个i位置能不能放入单调数列,以及放入i位置之前单调队列需要做哪些调整,才能继续维系单调队列

第一,如果单调队列的头元素已经超过了滑动窗口边界i-k+1且头元素不为空,那么就需要把头元素弹出,以此循环,直到头元素在滑动窗口内

第二,如果这次要加入的i位置在nums中的值是大于目前单调队列的头元素在nums中的值,那么就不符合单调队列了,就需要把原来的小的头元素弹出,以此循环比较头元素和i位置在nums中对应的值,进行弹出操作,直到头元素对应的值比i对应的值大,或者头元素为空为止

于是就可以把i位置安心地放入单调队列中了

但是

还需要考虑一个问题,我的结果集什么时候开始收集?

当然是从i的值等于k-1开始收集,收集n-k+1次即可,因此需要在入队操作后,加上对于结果集res的操作,这个操作当然是将本次滑动窗口对应的单调队列的出口元素在nums中对应的值赋值给res

最后,返回结果集res即可

代码如下:

	@Test
    public void test02(){
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] res = maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(res));
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deuqe = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int index = 0;
        for (int i = 0; i < n; i++) {
            while (!deuqe.isEmpty() && deuqe.peek() < (i - k + 1)) {
                deuqe.poll();
            }
            while (!deuqe.isEmpty() && nums[deuqe.peekLast()] < nums[i]) {
                deuqe.pollLast();
            }
            deuqe.offer(i);

            if (i >= k - 1) {
                res[index++] = nums[deuqe.peek()];
            }
        }
        return res;
    }

347.前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

关于大顶堆和小顶堆在java中数据结构知识如下:

在Java中，大顶堆（Max Heap）和小顶堆（Min Heap）是两种常用的基于二叉树的数据结构，它们都是堆（Heap）这种特殊完全二叉树的实现。堆通常用于实现优先队列，其中大顶堆的根节点是堆中的最大元素，而小顶堆的根节点是堆中的最小元素。Java标准库中没有直接以“大顶堆”或“小顶堆”命名的类，但PriorityQueue类可以实现这两种堆的功能。

PriorityQueue 类

java.util.PriorityQueue 是一个基于优先级堆的无界优先级队列。默认情况下，PriorityQueue 是一个小顶堆，但是你可以通过提供一个自定义的比较器（Comparator）来让它表现为大顶堆。

小顶堆示例

import java.util.PriorityQueue;  
  
public class MinHeapExample {  
    public static void main(String[] args) {  
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();  
        minHeap.add(10);  
        minHeap.add(5);  
        minHeap.add(20);  
        minHeap.add(1);  
  
        while (!minHeap.isEmpty()) {  
            System.out.println(minHeap.poll()); // 依次输出 1, 5, 10, 20  
        }  
    }  
}

大顶堆示例

要使用PriorityQueue实现大顶堆，你需要提供一个自定义的比较器，该比较器会反转元素的自然顺序（或者任何你想要的顺序）。

import java.util.Comparator;  
import java.util.PriorityQueue;  
  
public class MaxHeapExample {  
    public static void main(String[] args) {  
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());  
        maxHeap.add(10);  
        maxHeap.add(5);  
        maxHeap.add(20);  
        maxHeap.add(1);  
  
        while (!maxHeap.isEmpty()) {  
            System.out.println(maxHeap.poll()); // 依次输出 20, 10, 5, 1  
        }  
    }  
}

思路 : 这是我第一次在题目中使用到小顶堆这个数据结构,但是在这个题中又出奇地好用,因为只需要入堆时判断当前频率值是否大于小顶堆的堆顶的频率值,如果大于,那么就把小顶堆中的堆顶元素弹出,将当前的值放入堆中,否则则不做操作,以此循环

代码如下:

	@Test
    public void test03() {
        int[] nums = new int[]{1, 1, 1, 2, 2, 3};
        int k = 2;
        int[] res = topKFrequent(nums, k);
        System.out.println("前" + k + "个高频元素是 : " + Arrays.toString(res));
    }

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();  //用来存储nums中的元素和其出现次数的映射关系
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(pri -> pri[1]));
        //Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                //assert queue.peek() != null;
                if (!queue.isEmpty() && entry.getValue() > queue.peek()[1]) {
                    queue.poll();
                    queue.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            //assert queue.peek() != null;
            if (!queue.isEmpty()) res[i] = queue.poll()[0];
        }
        return res;
    }