算法day10-栈与队列（2）

目录

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

一、逆波兰表达式求值

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

 

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

 　　方法一：暴力法，直接以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

 

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.         }
8.         PriorityQueue<int[]> queue = new PriorityQueue<>((pair1, pair2)->pair2[1] - pair1[1]);
9.         //遍历哈希表，把对应的k-v存储到队列中
10.         for(Map.Entry<Integer,Integer> entry : map.entrySet()){
11.             queue.add(new int[]{entry.getKey(), entry.getValue()});
12.         }
14.         int[] res = new int[k];
15.         for(int i=0; i<k; i++){
16.             res[i] = queue.poll()[0];       //把key弹出来
17.         }
18.         return res;
19.     }
20. }
21. //时间复杂度: O(nlogk)
22. //空间复杂度: O(n)

复制代码

 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！