代码随想录算法训练营第十一天-239滑动窗口最大值、347前 K 个高频元素

前言
状态：239 超时，347 直接用的 Stream 流。
更新

        
05.31 初始记录
06.01 完成题目

初步题解

239 滑动窗口最大值

题目链接：(https://leetcode.cn/problems/sliding-window-maximum/description/)

暴力解法：循环判断最大值（超时）

        JAVA
        
      
public class LE239 {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        String s = scanner.nextLine();  
        int[] split = Arrays.stream(s.split(",")).mapToInt(Integer::parseInt).toArray();  
        int[] ints = maxSlidingWindow(split, Integer.parseInt(scanner.nextLine()));  
        for (int anInt : ints) {  
            System.out.println(anInt);  
        }  
    }  
  
    public static int[] maxSlidingWindow(int[] nums, int k) {  
        if (nums.length <= k) {  
            return new int[]{getMax(nums, 0, nums.length - 1)};  
        }  
  
        ArrayList<Integer> list = new ArrayList<>();  
        for (int i = 0; i <= nums.length - k; i++) {  
            int max = getMax(nums, i, i + k - 1);  
            list.add(max);  
        }  
        return list.stream().mapToInt(i -> i).toArray();  
    }  
  
    private static int getMax(int[] nums, int i, int j) {  
        int max = Integer.MIN_VALUE;  
        for (int k = i; k <= j; k++) {  
            max = Math.max(max, nums[k]);  
        }  
        return max;  
    }  
}

347 前 K 个高频元素

题目链接：(https://leetcode.cn/problems/top-k-frequent-elements/description/)

直接用 Stream 流的解法，估计上班会用这个。。。甚至可以优化成一行

        JAVA
        
      
public static int[] topKFrequent(int[] nums, int k) {  
    // map用于计数  
    TreeMap<Integer, Integer> map = new TreeMap<>();  
    for (int num : nums) {  
        map.put(num, map.getOrDefault(num, 0) + 1);  
    }  
  
    return map.entrySet().stream()  
            .sorted((o1, o2) -> o2.getValue() - o1.getValue())  
            .limit(k)  
            .map(Map.Entry::getKey)  
            .mapToInt(i -> i)  
            .toArray();  
}

看解析

239 滑动窗口最大值

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0239.滑动窗口最大值.html#思路)

思路：这题放在队列专题，肯定是要用到队列思想的。按暴力的解法，求最大值的那个循环（这样效率就是 O(n * k)），在这边可以用单调队列解决。
其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。Java 中没有直接支持单调队列，需要我们自己来实现一个单调队列

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

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

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

        JAVA
        
      
/**  
 * 定义一个单调队列  
 */  
static class MyQueue {  
    Deque<Integer> deque = new LinkedList<>();  
  
    public void push(int num) {  
        while (!deque.isEmpty() && num > deque.getLast()) {  
            deque.removeLast();  
        }  
        deque.add(num);  
    }  
  
    /**  
     * 判断队顶元素是否是要移除的元素  
     */  
    public void pull(int num) {  
        if (!deque.isEmpty() && deque.peek() == num) {  
            deque.poll();  
        }  
    }  
  
    public int peek() {  
        return deque.peek();  
    }  
}  
  
public static int[] maxSlidingWindow(int[] nums, int k) {  
    MyQueue myQueue = new MyQueue();  
    for (int i = 0; i < k; i++) {  
        myQueue.push(nums[i]);  
    }  
  
    int j = 0;  
    int[] ints = new int[nums.length - k + 1];  
    ints[j++] = myQueue.peek();  
    for (int i = k; i <nums.length; i++) {  
        // 窗口滑动，移除元素（移除时要判断元素是否在单调队列内）  
        myQueue.pull(nums[i - k]);  
        // 窗口滑动，添加最新元素到单调队列  
        myQueue.push(nums[i]);  
        // 获取单调队列队顶元素（根据定义的规则，一定是区间内最大的）  
        ints[j++] = myQueue.peek();  
    }  
    return ints;  
}

347 前 K 个高频元素

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0347.前K个高频元素.html)

这题属于：前 K 个大数问题。这种问题一般用大顶堆（根节点最大）或小顶堆（根节点最小）。需要使用小顶堆，因为要统计最大前 k 个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前 k 个最大元素。

emmmmm 感觉和 Stream 流没有什么区别（可能在于他用的容器吧）。

        JAVA
        
      
/*Comparator接口说明:
 * 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面
 * 对于队列：排在前面意味着往队头靠
 * 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
 *                                从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
 * */
class Solution {
    //解法1：基于大顶堆实现
    public int[] topKFrequent1(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) -> pair2[1] - pair1[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {//大顶堆需要对所有元素进行排序
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) { //依次从队头弹出k个,就是出现频率前k高的元素
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
    //解法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;
    }
}