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

239. 滑动窗口最大值

题目链接：滑动窗口最大值
文档讲解：代码随想录
状态：忘了

思路1：使用优先队列来维护滑动窗口中的最大值，确保在每次滑动时能够高效地找到最大值。时间复杂度是 O(n log k)。
题解：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 使用优先队列（最大堆），按值降序排序
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        int n = nums.length;
        int m = n - k + 1;
        int idx = 0;
        int[] ans = new int[m];

        // 遍历数组
        for (int i = 0; i < n; i++) {
            // 将当前元素的索引和值加入优先队列
            q.add(new int[]{i, nums[i]});
            
            // 当窗口形成时
            if (i >= k - 1) {
                // 移除不在当前窗口范围内的元素
                while (q.peek()[0] <= i - k) {
                    q.poll();
                }
                // 当前窗口的最大值是堆顶元素的值
                ans[idx++] = q.peek()[1];
            }
        }
        return ans;
    }
}

思路2：利用单调队列(一头进,一头出)模型滑动窗口。
题解：

/**
 * 思路:利用单调队列(一头进,一头出)模型滑动窗口,注意单调队列中维护的是下标不是元素值
 * 1.遍历元素,当单调队列中元素为空时,元素加入队列
 * 2.当遍历到的元素x比队列中的头元素要大时,从队尾往队头所有比遍历到的当前元素小的元素出队,最后在队尾中存入x
 * 3.当遍历到的元素x比队列头中的元素要小时,元素加到队尾
 * 4.在这个过程中,如果队头元素的下标超出滑动窗口范围,则队列头元素出队
 */
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int i = 0, j = 0;
        while (i < n) {
//            deque.peekFirst()队列头元素的下标 < i - k + 1(队列左边界),弹出队列头元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();//pop相当于pollFirst方法
            }
            //当遍历到的元素比队列中的元素要大时,从队尾往队头所有比遍历到的当前元素小的元素出队
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            //当单调队列中元素为空，或者遍历到的元素比队列尾中的元素要小时,元素加到队尾
            deque.addLast(i);
            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if (i >= k - 1) {
                result[j++] = nums[deque.peekFirst()];
            }
            i++;
        }
        return result;
    }

347.前 K 个高频元素

题目链接：347.前 K 个高频元素
文档讲解：代码随想录
状态：还行

思路:

• 1.要统计元素出现频率,HashMap
• 2.对频率排序,优先队列
• 3.找出前K个高频元素

题解：

    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] res = new int[k];
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((p1, p2) -> p2[1] - p1[1]);
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
        }
        for (int i = 0; i < k; i++) {
            res[i] = Objects.requireNonNull(priorityQueue.poll())[0];
        }
        return res;
    }