代码随想录算法训练营二十四期第十三天|LeetCode239. 滑动窗口最大值、LeetCode347. 前 K 个高频元素

一、LeetCode239. 滑动窗口最大值

题目链接：239. 滑动窗口最大值
利用一个先进先出的队列来存放当窗口中的最大值元素，以及在它后面依次减小的元素（也就是从最大值开始，按照非递增顺序，存放最大的一组元素）。
如此队头就是当前窗口的最大值，向右滑动时，右两个元素在变动（窗口左边界元素移出，窗口右边界插入一个元素），我们要分别处理。如果左边界移除的元素恰好是队头（也就是上一个窗口的最大值），我们就要同时将队头元素弹出，否则队头不做处理。然后处理右边界插入的元素，让该元素依次与队列的队尾左比较，如果大于队尾，将队尾移除，直到队尾元素大于等于该元素时，将该元素插入队尾（要保持队列非递增的性质）。
代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int left = -1;
        int right = -1;//指针从-1索引开始，利用左开右闭的原则
        int[] result = new int[nums.length - k + 1];//接受滑动窗口最大值的数组
        int index = 0;
        ArrayDeque<Integer> que = new ArrayDeque<>();//用一个先进先出的队列来存放当前窗口内最大的值以及在它后面小于等于它的元素，这里要重点注意，（队列中的队头就是当前窗口的最大值，同时在向右滑动时，如果最大之元素滑出了窗口，那么将队列的对头弹出，插入时，要依次比较当前元素与队尾的大小，如果大于队尾，将队尾删除，在比较下一个队尾，直到队尾元素大于等于当前元素，要保证队列的元素是按照非递增的顺序存放的。）
        while(right < nums.length) {//注意right指针越界
            if(right - left < k) {//如果当前窗口长度小于k,将right向右移，同时将nums[right]按照规则插入队列
                right++;
                while(!que.isEmpty() && que.getLast() < nums[right]) {
                    que.pollLast();
                }
                que.addLast(nums[right]);
            }else {//如果窗口长度等于k，那么将队列的队头，也就是当前窗口的最大值放入结果集中（注意不是删除队头）
                result[index++] = que.getFirst();
                left++;
                if(que.getFirst() == nums[left]) {//移动窗口左边界，如果此时被移出的元素是队头元素，那么将队头删除
                    que.pollFirst();
                }
                right++;//移动右边界
                if(right == nums.length) break;//如果右边界溢出，跳出循环，否则继续将窗口最右边的元素nums[right]按照规则插入队列
                while(!que.isEmpty() && que.getLast() < nums[right]) {
                    que.pollLast();
                }
                que.addLast(nums[right]);
            }
            
        }  
        return result;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度为O（n），空间复杂度为O（n）

二、LeetCode347. 前 K 个高频元素

题目链接：347. 前 K 个高频元素
首先利用Map哈希表来统计数组中每个元素出现的个数。然后实现一个基于小顶堆（或大顶堆）的队列来对每个元素按照出现频率进行排序（注意队列中每个元素是一个长度为2的数组，用来存放的出现的元素和频率）。
代码如下：
基于小顶堆实现：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer>map = new HashMap();//用来统计每个元素出现的个数

        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i], 0) + 1);
        }
        //根据每个元素出现的个数，来对每个元素排序同时将前k个元素放入队列中
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            pq.add(new int[]{entry.getKey(),entry.getValue()});
            if(pq.size() > k) {
                pq.poll();
            }
        }
        //此时队列中的元素包含了数组中出现的前k个元素
        int[] ans = new int[k];//将队列中的前k个元素放入一个结果数组里返回
        for(int i = k - 1; i >= 0; i--) {
            ans[i] = pq.poll()[0];
        }
        
        return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

基于大顶堆实现：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer>map = new HashMap();//用来统计每个元素出现的个数

        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i], 0) + 1);
        }
        //基于大顶堆实现队列，根据每个元素出现的个数，来对每个元素排序同时放入队列中
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            pq.add(new int[]{entry.getKey(),entry.getValue()});
        }
        //此时队列中的元素是是从大到小排序的，包含了数组中出现的全部元素，我们只需要将前k个元素
        int[] ans = new int[k];//将队列中的前k个元素放入一个结果数组里返回
        for(int i = k - 1; i >= 0; i--) {
            ans[i] = pq.poll()[0];
        }
        
        return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结

要掌握优先队列的应用，大顶堆小顶堆的原理和实现方法。