day13 打卡239. 滑动窗口最大值 347.前 K 个高频元素

239. 滑动窗口最大值

239题目链接

1.看了视频在写的

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int index = 0;
        int[] result = new int[nums.length - k + 1];
        ArrayDeque<Integer> que = new ArrayDeque<Integer>();
        for (int i = 0 ; i<nums.length ; i++) {
            // 检查队列里的元素是否在k的范围之内
            while (!que.isEmpty() && !(que.peek() >= index && que.peek() <= index+k-1)) {
                que.poll();
            }

            // 如果队列里的元素<要加入的元素，队列里的元素都弹出
            // 因为要保证单调的，从大到小
            // 不然可能出现 队列里有3，1，2。等3出去了，进来1，跟顶部1比较，但是2更大
            while (!que.isEmpty() && nums[que.peekLast()]<nums[i]) {
                que.pollLast();
            }
            que.offer(i);

            if (i>=k-1) {
                result[index++] = nums[que.peek()];
            }
        }
        return result;
    }
}

347.前 K 个高频元素

347题目链接

1.看视频后写的代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }

        // 创建小顶堆，从小到大。保存的是数组，0:num，1:num出现的次数
        PriorityQueue<int[]> que = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            int count = entry.getValue();
            if (que.size() >= k) {
                // 每次将多余的数值弹出
                if (que.peek()[1] < count) {
                    que.poll();
                    que.add(new int[]{entry.getKey(), count});
                }
            } else {
                que.add(new int[]{entry.getKey(), count});
            }
        }

        int[] result = new int[k];
        for (int i = k-1; i>=0 ; i--) {
            result[i] = que.poll()[0];
        }
        return result;
    }
}

参考资料

代码随想录