找回密码
 立即注册
首页 业界区 科技 算法day10-栈与队列(2)

算法day10-栈与队列(2)

鞠彗云 2025-6-7 10:18:25
目录


  • 逆波兰表达式求值
  • 滑动窗口最大值
  • 前K个高频元素
一、逆波兰表达式求值

  https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/?envType=problem-list-v2&envId=8At1GmaZ
1.png

 
  1. class Solution {
  2.     public int evalRPN(String[] tokens) {
  3.         Deque<String> stack = new ArrayDeque<>();
  4.         for(String s : tokens){
  5.             if(s.equals("+")){
  6.                 int n2 = Integer.parseInt(stack.pop());
  7.                 int n1 = Integer.parseInt(stack.pop());
  8.                 int sum = n2 + n1;
  9.                 stack.push(String.valueOf(sum));
  10.             }else if(s.equals("-")){
  11.                 int n2 = Integer.parseInt(stack.pop());
  12.                 int n1 = Integer.parseInt(stack.pop());
  13.                 int n = n1 - n2;
  14.                 stack.push(String.valueOf(n));
  15.             }else if(s.equals("*")){
  16.                 int n2 = Integer.parseInt(stack.pop());
  17.                 int n1 = Integer.parseInt(stack.pop());
  18.                 int n = n1 * n2;
  19.                 stack.push(String.valueOf(n));
  20.             }else if(s.equals("/")){
  21.                 int n2 = Integer.parseInt(stack.pop());
  22.                 int n1 = Integer.parseInt(stack.pop());
  23.                 int n = n1 / n2;
  24.                 stack.push(String.valueOf(n));
  25.             }else{
  26.                 stack.push(s);
  27.             }
  28.         }
  29.         return Integer.parseInt(stack.pop());
  30.     }
  31. }
复制代码
二、滑动窗口最大值

  https://leetcode.cn/problems/sliding-window-maximum/description/?envType=problem-list-v2&envId=8At1GmaZ
2.png

   方法一:暴力法,直接以3为窗口进行滑动,在每个窗口内都取最大值。
  方法二:采用单调队列的方法,始终维护一个单调队列。每个窗口都把最大的元素放在队头,所以每次弹出的也是队头元素,这样可以利用到前面窗口的信息。
  1. class Solution {
  2.     public int[] maxSlidingWindow(int[] nums, int k) {
  3.         int n = nums.length;
  4.         int[] res = new int[n-k+1];
  5.         Deque<Integer> queue = new ArrayDeque<>();
  6.         int index = 0;
  7.         
  8.         for(int i = 0; i<n; i++){
  9.             //1.新入队的元素若头节点的索引已经超过以i结尾的窗口的起点,就把头节点去掉
  10.             if(!queue.isEmpty() && queue.peek() < i-k+1){
  11.                 queue.poll();       //把头节点从队头剔除
  12.             }
  13.             while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
  14.                 queue.pollLast();           //把比新加入的元素小的元素从末尾剔除
  15.             }
  16.             queue.offer(i);
  17.             if(i >= k-1){
  18.                 res[index] = nums[queue.peek()];
  19.                 index++;
  20.             }
  21.         }
  22.         return res;
  23.     }
  24. }
  25. //时间复杂度:O(N)
  26. //空间复杂度:O(k)
复制代码
 
三、前k个高频元素

  https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=problem-list-v2&envId=8At1GmaZ
3.png

 
  1. class Solution {
  2.     public int[] topKFrequent(int[] nums, int k) {
  3.         Map<Integer, Integer> map = new HashMap<>();
  4.         for(int num : nums){
  5.             map.put(num, map.getOrDefault(num,0)+1);       //统计每个元素出现的次数
  6.         }
  7.         PriorityQueue<int[]> queue = new PriorityQueue<>((pair1, pair2)->pair2[1] - pair1[1]);
  8.         //遍历哈希表,把对应的k-v存储到队列中
  9.         for(Map.Entry<Integer,Integer> entry : map.entrySet()){
  10.             queue.add(new int[]{entry.getKey(), entry.getValue()});
  11.         }
  12.         int[] res = new int[k];
  13.         for(int i=0; i<k; i++){
  14.             res[i] = queue.poll()[0];       //把key弹出来
  15.         }
  16.         return res;
  17.     }
  18. }
  19. //时间复杂度: O(nlogk)
  20. //空间复杂度: O(n)
复制代码
 

来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
您需要登录后才可以回帖 登录 | 立即注册