【随想录】Day13—第五章 栈与队列part03

本文主要是介绍【随想录】Day13—第五章 栈与队列part03，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目1: 239. 滑动窗口最大值

• 题目链接：239. 滑动窗口最大值

---

1- 思路

• 滑动窗口移动的过程很像是一个队列，实现一个 单调队列 —— 维护元素的单调顺序

自定义单调队列

• ① 删除
  • 如果当前栈非空、被删元素值等于队列头元素，此时直接弹出
• ②加入
  • 此时加入元素，如果值大于 队列头元素，此时将队列清空，再加入该值
• ③返回队列头元素
  • deque.peek()

class MyQueue{Deque<Integer> deque = new LinkedList<>();// poll,删 void poll(int val){if(!deque.isEmpty() && val==deque.peek()){deque.poll();}}// addvoid add(int val){while(!deque.isEmpty() && val>deque.getLast()){deque.removeLast();}deque.add(val);}int peek(){return deque.peek();}}

---

2- 题解

⭐滑动窗口最大值 ——题解思路

class MyQueue{Deque<Integer> deque = new LinkedList<>();// addpublic void add(int val){while(!deque.isEmpty() && val>deque.getLast()){deque.removeLast();}deque.add(val);}// removepublic void poll(int val){if(!deque.isEmpty() && val==deque.peek()){deque.poll();}}// peekint peek(){return deque.peek();}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {MyQueue myQueue = new MyQueue();// 先加 kint[] res = new int[nums.length-k+1];int index = 0;for(int i = 0 ; i < k;i++){myQueue.add(nums[i]);}res[index++] = myQueue.peek();// 遍历剩余元素for(int i = k;i<nums.length;i++){myQueue.poll(nums[i-k]);myQueue.add(nums[i]);res[index++] = myQueue.peek();}return res;}
}

---

题目2: 347.前 K 个高频元素

• 题目链接：347. 前 K 个高频元素

---

1- 思路

• 本题需要返回的是，出现频率为前 k 高的元素，
• 则此时需要统计 元素 和 频率的映射，因此需要用到 HashMap

① 通过 HashMap统计频率 ——> ②遍历 HashMap存入优先级队列 ——> ③遍历优先级队列求结果

---

2- 实现

⭐前 K 个高频元素 ——题解思路

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<int[] > pq = new PriorityQueue<>((o1,o2) -> (o1[1]-o2[1]));// 遍历mapfor(Map.Entry<Integer,Integer> entry:map.entrySet()){// 小于 k 小顶堆无需弹出if(pq.size()<k){pq.add(new int[]{entry.getKey(),entry.getValue()});}else{if(entry.getValue() > pq.peek()[1]){ // 判断当前元素是否大于小顶堆的头pq.poll();pq.add(new int[]{entry.getKey(),entry.getValue()});}}}int[] ans = new int[k];for(int i=k-1;i>=0;i--){ans[i] = pq.poll()[0];}return ans;}
}

---

这篇关于【随想录】Day13—第五章 栈与队列part03的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---