DAY13|239.滑动窗口的最大值，347.前 K 个高频元素

239.滑动窗口的最大值

文档讲解：滑动窗口的最大值

状态：单调队列，保持队列中元素为递增或递减，队列头为最大值或最小值；

思路：
1、编写一个递增的单调队列来维护可能为最大值的元素；
2、当有新元素加入队尾时，判断加入元素是否比队尾元素大，如果大则将队尾元素直接remove掉，直到加入元素比队尾元素小，将元素加入到队尾；
3、此时队列就保持一个递增的状态，当窗口向后移动时，判断窗口左侧需要舍弃的元素是否是队列头最大值的那个元素，如果时，则这时需要舍弃掉队头，即poll，这一步很关键；
4、最后每次窗口滑动时，将队列头的peek元素加入到返回结果数组中即可；
代码：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] resultArr = new int[nums.length - k + 1];
        MyQueue queue = new MyQueue();
        int left = 0;
        int right = left + k -1;
        int index = 0;
        for (int i = left; i <= right ; i++) {
            queue.add(nums[i]);
        }
        resultArr[index] = queue.getMax();
        while (right < nums.length - 1) {
            int removeNum = nums[left];
            right++;
            left++;
            index++;
            queue.poll(removeNum);
            queue.add(nums[right]);
            resultArr[index] = queue.getMax();
        }
        return resultArr;
    }

    static class MyQueue {

        Deque<Integer> deque = new ArrayDeque<>();

        void poll(int val) {
            if (!deque.isEmpty() && val == deque.getFirst()) {
                deque.removeFirst();
            }
        }

        void add(int val) {
            while (!deque.isEmpty() && val > deque.getLast()) {
                deque.removeLast();
            }
            deque.addLast(val);
        }

        int getMax() {
            return deque.getFirst();
        }
    }
}

347.前 K 个高频元素

文档讲解：前K个高频元素

状态：之前没用过优先级队列，所以自己参考上题使用单调队列和map通过了，但是耗时很长；

思路1

思路：

1、先通过map对每个数字出现的次数进行统计；

2、编写一个单调递增的队列，队列头是最大元素，队尾是最小元素，每次从队尾加入元素时，判断加入元素是否比队尾大，如果大的话则将队尾元素先放入一个栈中，再从此此操作，直到将元素放入队列中，放入后将栈中元素依次出栈加入队列的队尾；

3、依次从队列头poll出k个元素返回；

代码：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        MyQueue queue = new MyQueue();
        int[] result = new int[k];
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num)+1);
            } else {
                map.put(num, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.push(entry);
        }
        for (int i = 0; i < result.length; i++) {
            if (!queue.isEmpty()) {
                Map.Entry<Integer, Integer> temp = queue.poll();
                result[i] = temp.getKey();
            }
        }
        return result;
    }

    static class MyQueue {

        Deque<Map.Entry<Integer, Integer>> deque = new LinkedList<>();
        Stack<Map.Entry<Integer, Integer>> tempStack =  new Stack<>();

        private void push(Map.Entry<Integer, Integer> entry) {
            while (!deque.isEmpty() && deque.getLast().getValue() < entry.getValue()) {
                Map.Entry<Integer, Integer> tempEntry = deque.removeLast();
                tempStack.push(tempEntry);
            }
            deque.addLast(entry);
            while (!tempStack.isEmpty()) {
                deque.addLast(tempStack.pop());
            }
        }

        private Map.Entry<Integer, Integer> poll() {
            return deque.removeFirst();
        }

        private Map.Entry<Integer, Integer> peek() {
            return deque.getFirst();
        }

        private boolean isEmpty() {
            return deque.isEmpty();
        }
    }
}

思路二

思路：

1、通过PriorityQueue+Map实现；优先级队列的解题思路后续补上;之前自己没用过这个容器；

代码：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[k];
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
        for (int i = 0; i < result.length; i++) {
            result[i] = pq.poll()[0];
        }
        return  result;
    }
 }