239. 滑動(dòng)窗口最大值

題目連接：https://leetcode.cn/problems/sliding-window-maximum/
思路一：使用單調(diào)隊(duì)列簿透，從小到大姥饰，不停的pop(val); 不停的push(val)羹令，在peek的值都是要獲取的值
pop(val)：如果隊(duì)列頭元素正是當(dāng)前的最大值鲤屡，則彈出poll()這個(gè)值
push(val):判斷隊(duì)尾的元素比當(dāng)前值小則直接彈出，最后添加這個(gè)值
peek:獲取隊(duì)列頭的元素

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 個(gè)高頻元素

題目連接：https://leetcode.cn/problems/top-k-frequent-elements/
思路：先使用hashMap統(tǒng)計(jì)頻率，肪凛，然后使用最小堆堰汉，小于k的時(shí)候一直添加，如果=k的時(shí)候伟墙，在往里面添加的時(shí)候翘鸭，看當(dāng)前要添加的元素比堆頂?shù)淖钚≡剡€大的時(shí)候，就將最小堆頂?shù)脑貜棾龃量诎研略靥砑舆M(jìn)去就乓。然后遍歷一次彈出最小堆

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;
    }
}