239. 滑动窗口最大值

题目连接：https://leetcode.cn/problems/sliding-window-maximum/
思路一：使用单调队列，从小到大，不停的pop(val); 不停的push(val)，在peek的值都是要获取的值
pop(val)：如果队列头元素正是当前的最大值，则弹出poll()这个值
push(val):判断队尾的元素比当前值小则直接弹出，最后添加这个值
peek:获取队列头的元素

class Solution {
    public class MyQueue {
        private ArrayDeque<Integer> queue = new ArrayDeque<>();
        public void pop(int val) {
            if (!queue.isEmpty() && val == queue.peek()) {
                queue.poll();
            }
        }

        public void add(int val) {
            while (!queue.isEmpty() && val > queue.peekLast()){
                queue.pollLast();
            }
            queue.offer(val);
        }
        
        public int peek() {
            return queue.peek();
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        MyQueue queue = new MyQueue();
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        int index = 0;
        result[index++] = queue.peek();
        for (int i = k; i < nums.length; i++){
            System.out.println(i - k);
            queue.pop(nums[i - k]);
            queue.add(nums[i]);
            result[index++] = queue.peek();
        }
        return result;
    }
}

思路二、原理和思路一同样，不过此方法queue存放的是索引

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] result = new int[len - k + 1];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        int index = 0;
        for (int i = 0; i < len; i++){
            if (!queue.isEmpty() && queue.peek() == i - k) {
                queue.poll();
            }
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.offer(i);
            if (i >= k - 1) {
                result[index++] = nums[queue.peek()];
            }
        }
        return result;
    }
}

347. 前 K 个高频元素

题目连接：https://leetcode.cn/problems/top-k-frequent-elements/
思路：先使用hashMap统计频率，，然后使用最小堆，小于k的时候一直添加，如果=k的时候，在往里面添加的时候，看当前要添加的元素比堆顶的最小元素还大的时候，就将最小堆顶的元素弹出，在把新元素添加进去。然后遍历一次弹出最小堆

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new 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[]> queue = new PriorityQueue<>((e1, e2)->e1[1] - e2[1]);
        for (Map.Entry<Integer, Integer> entry:map.entrySet()){
            int key = entry.getKey();
            int value = entry.getValue();
            System.out.println(key + " " + value);
            if (queue.size() < k) {
                queue.add(new int[]{key, value});
            } else {
                if (queue.peek()[1] < value) {
                    queue.poll();
                    queue.add(new int[]{key, value});
                }
               
            }
        }
        for (int i = k - 1; i >= 0; i--) {
            result[i] = queue.poll()[0];
        }
        return result;
    }
}