算法训练营day11 | {150.逆波兰表达式求值, 239.滑动窗口最大值, 347.前K个高频元素}

第五章栈与队列part02，单调递减队列，小顶堆（JAVA内置了优先队列默认构建的就是小顶堆）。

150. 逆波兰表达式求值

• 题目链接：150.逆波兰表达式求值
• 文档讲解：代码随想录–150.逆波兰表达式求值
• 状态：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

1.1 解题过程

• 把运算符作为中间结点，按照二叉树后续遍历的规则就能得到逆波兰表达式，逆波兰实际上就是对算法表达式的序列化，以后续遍历的方式。
  ▶

  150. 逆波兰表达式求值

  class Solution {
      public int evalRPN(String[] tokens) {
          Deque<Integer> stack = new ArrayDeque<>();
          Set<String> op = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
          for (int i = 0; i < tokens.length; i++) {
              if (!op.contains(tokens[i])) {
                  stack.push(Integer.parseInt(tokens[i]));
              } else {
                  int r = stack.pop();
                  int l = stack.pop();
                  int res;
                  if("+".equals(tokens[i])) {
                      res = l + r;
                  } else if ("-".equals(tokens[i])) {
                      res = l - r;
                  } else if ("*".equals(tokens[i])) {
                      res = l * r;
                  } else {
                      res = l / r;
                  }
                  stack.push(res);
              }
          }
          return stack.pop();
      }
  }

239. 滑动窗口最大值

• 题目链接：239. 滑动窗口最大值
• 文档讲解：代码随想录–239. 滑动窗口最大值
• 视频讲解：单调队列正式登场！| LeetCode：239. 滑动窗口最大值
• 状态：按照题意去每个长为k的滑动窗口遍历得到最大值，时间复杂度为O(n*k)。

2.1 看完代码随想录的想法

• 单调队列是一种特殊的数据结构，其元素在队列中始终保持单调递增或单调递减的规律。它通过双端操作（队首和队尾）维护一个隐含的单调子序列，而非实际存储所有元素，从而在插入或者删除时高效舍弃破坏单调性的无效数据。。

• 看了视频讲解，自己构建一个单调递减队列，有如下特性：

  • 队头始终为当前窗口的最大值；
  • 入队时，新元素入队之前，会从队尾移除所有比它小的元素；
  • 出队时，依据整数数组，如果队头==nums数组遍历到的元素，则真的执行出队操作。

2.2 小结

• 主要思想是队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

• 自定义一个单调递减队列，然后遍历nums数组就好，遍历这一块写得不是很优雅，要完善一下：

  ▶

  239. 滑动窗口最大值

  class MyQueue {
  
      Deque<Integer> queue;
  
      public MyQueue(Deque<Integer> queue) {
          this.queue = queue;
      }
  
      public Integer popEle(int ele) {
          if (!queue.isEmpty() && queue.peekFirst() == ele) {
              return queue.pollFirst();
          }
          return null;
      }
  
      public void pushEle(int ele) {
          while (!queue.isEmpty() && queue.peekLast() < ele) {
              queue.pollLast();
          }
          queue.offerLast(ele);
      }
  
      public Integer getMaxValue() {
          return queue.peekFirst();
      }
  }
  
  class Solution {
      public int[] maxSlidingWindow(int[] nums, int k) {
          int[] res = new int[nums.length - k + 1];
          MyQueue myQueue = new MyQueue(new ArrayDeque<>());
          for (int j = 0; j < k; j++) myQueue.pushEle(nums[j]);  // 入队k个
          int left = 0;
          for(int right = k; right < nums.length; right++) {
              res[left] = myQueue.getMaxValue();  // 记录的是进入下一个窗口之前的最大值
              myQueue.popEle(nums[left]);
              left++;
              myQueue.pushEle(nums[right]);
          }
          res[left] = myQueue.getMaxValue();
          return res;
      }
  }

347. 前K个高频元素

• 题目链接：347.前K个高频元素
• 文档讲解：代码随想录–347.前K个高频元素
• 视频讲解：优先级队列正式登场！大顶堆、小顶堆该怎么用？| LeetCode：347.前 K 个高频元素
• 状态：想到一个按Map的value排序的方法。

3.1 看完题目的想法

• 复盘一遍怎么按照map的value排序：

  Map<String, Integer> map = new HashMap<>();
  
  map.put("a", 99);
  map.put("b", -5);
  map.put("c", 128);
  
  List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
  list.sort((o1, o2) -> o2.getValue() - o1.getValue());  // 自定义降序排序规则

• 第一种解法：
  ▶

  347. 前K个高频元素

  class Solution {
      public int[] topKFrequent(int[] nums, int k) {
          int[] res = new int[k];
          Map<Integer, Integer> map = new HashMap<>();
          for(int num : nums) {
              map.put(num, map.getOrDefault(num, 0) + 1);
          }
          // 1. 转成list
          ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
          // 2. 对value排序
          list.sort((o1, o2) -> o2.getValue() - o1.getValue());
          // 3. 取前k个
          for (int i = 0; i < k; i++) {
              res[i] = list.get(i).getKey();
          }
          return res;
      }
  }

3.2 看完代码随想录的想法

• （解法二）：只维护一个k个结点的小顶堆，最先pop的是根结点（最小的），这样剩下的就是k个最大的。
  • 问题是小顶堆怎么写？今天是第一次写啊。

JAVA中怎么构建小顶堆？

Java中有内置的优先队列PriorityQueue，默认就是小顶堆(Min Heap)。

• 常用API

  含义	方法
  插入元素	offer(e)
  取出并删除堆顶	poll()
  查看堆顶	peek()
  当前元素的个数	size()
  是否为空	isEmpty()

• 插入的时间复杂度O(logn)、删除的时间复杂度O(logn)、取堆顶O(1)

1. 默认构造—小顶堆

   PriorityQueue<Integer> minHeap = new PriorityQueue<>();
   //PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.naturalOrder());
   minHeap.offer(3);
   minHeap.offer(1);
   minHeap.offer(2);
   
   System.out.println(minHeap.poll()); // 1
   System.out.println(minHeap.poll()); // 2
   System.out.println(minHeap.poll()); // 3

2. 构建大顶堆
   1. 数值类型

      PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

   2. 自定义比较器，按a[0]排序的小顶堆

      PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

3. 注意事项：
   1. PriorityQueue的遍历不是有序的，遍历顺序不等于对序，只有poll()才能保证顺序：

      for(int x : minHeap) {
       System.out.println(x);
      }

   2. 堆中不能存放null：

      minHeap.offer(null); // 空指针异常

结合leetcode题解写出小顶堆

• 复杂度分析
  • 时间复杂度：O(NlogN)，因为我们遍历出现次数数组(长度为N)，由于堆的大小至多为k，因此每次堆操作需要O(logk)的时间，共需O(NlogN)的时间。
  • 空间复杂度：O(N)，哈希表的大小为O(N)，堆的大小为O(k)，共计O(N)。
    ▶

    347. 前K个高频元素(优先队列)

    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            int[] res = new int[k];
            Map<Integer, Integer> occur = new HashMap<>();
            for (int num : nums) {
                occur.put(num, occur.getOrDefault(num, 0) + 1);
            }
            // 定义一个小顶堆
            // 每个数组元素，第一个存放key，第二个存放value
            PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            for (Map.Entry<Integer, Integer> e : occur.entrySet()) {
                int num = e.getKey();
                int cnt = e.getValue();
                if (queue.size() < k) {
                    queue.offer(new int[]{num, cnt});
                } else if (!queue.isEmpty() && queue.peek()[1] < cnt) {
                    queue.poll();
                    queue.offer(new int[]{num, cnt});
                }
            }
            int j = 0;
            while(!queue.isEmpty()) {
                res[j++] = queue.poll()[0];
            }
            return res;
        }
    }

4. 栈与队列总结

主要还是边写题，边熟悉JAVA语言内置的API

• Deque–模拟栈和队列
• 单调递增/递减队列–保证队列中的元素始终是单调的，也用Deque自定义这种数据结构实现
• 大顶堆/小顶堆–在Java中内置了优先级队列在实现这个数据结构，对外只提供offer()、poll()、peek()方法，看起来像队列，其实就是一个披着队列外衣的堆，只用维护部分数据有序。

5. Other

• 今天打了第482周的周赛
  • 第一题：前缀和数组 + 从后往前遍历取数组元素的最小值；
  • 第三题：和用哈希表来判断集合中的某个元素是否曾经出现过。判断余数是否陷入死循环。