Day22——队列和栈专题

约定不等于承诺〃 2024-04-01 12:08 63阅读 0赞

#### 文章目录 ####

*   *   *  6.滑动窗口最大值
         *  7. 前 K 个高频元素

--------------------

#### 6.滑动窗口最大值 ####

**思路**：设计单调队列的时候，pop，和push操作要保持如下规则：

1.  pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
2.  push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问`que.front()`就可以返回当前窗口的最大值。

//利用双端队列手动实现单调队列
    /**
     * 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
     * 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
     */
    class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            ArrayDeque<Integer> deque = new ArrayDeque<>();
            int n = nums.length;
            int[] res = new int[n - k + 1];
            int idx = 0;
            for(int i = 0; i < n; i++) {
        
                // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
                // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
                while(!deque.isEmpty() && deque.peek() < i - k + 1){
        
                    deque.poll();
                }
                // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
                while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
        
                    deque.pollLast();
                }
    
                deque.offer(i);
    
                // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
                if(i >= k - 1){
        
                    res[idx++] = nums[deque.peek()];
                }
            }
            return res;
        }
    }

#### 7. 前 K 个高频元素 ####

**关于堆：**

如果面试题中要求求出一个动态数据集中的最大值或者最小值，那么一般可以考虑使用优先队列（堆）来解决问题  
Java 中优先队列（堆） PriorityQueue 的默认情况下是一个最小堆，如果要使用最大堆，那么在调用构造函数时就需要传入 Comparator 的实现类自定义比较排序的规则。 PriorityQueue 实现了接口 Queue，常用函数有：

*  offer(e)：将元素 e 放入堆中
 *  poll()：删除堆顶元素
 *  peek()：返回位于堆顶的元素，但该元素并不出堆，还在堆中

**思路：优先队列**

我们可以通过优先队列维护这k个前 K 个高频元素（限制堆的大小为k），维护的依据是元素的出现次数，为此我们可以用一个map对元素和其出现次数进行绑定，维护一个小根堆，重写的排序规则就是根据map的entry对象中的出现次数进行排序（小根堆）。

当我们遍历map集合时，若队列未满，则将entry直接入堆，若满了，则比较当前元素的出现次数是否 >堆顶元素，是则弹出堆顶元素然后当前元素入堆即可！最终堆中的这k个元素即为 前 K 个高频元素。

**实现代码：**

//解法2：基于小顶堆实现
        public int[] topKFrequent2(int[] nums, int k) {
        
            Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
            for(int num:nums){
        
                map.put(num,map.getOrDefault(num,0)+1);
            }
            //在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
            //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
            PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
            for(Map.Entry<Integer,Integer> entry:map.entrySet()){
        //小顶堆只需要维持k个元素有序
                if(pq.size()<k){
        //小顶堆元素个数小于k个时直接加
                    pq.add(new int[]{
        entry.getKey(),entry.getValue()});
                }else{
        
                    if(entry.getValue()>pq.peek()[1]){
        //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                        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;
        }
    }