代码随想录算法训练营第十三天｜239-347

LeetCode 239.滑动窗口最大值

这道题其实还挺有意思的， 一个直观的想法是在遍历时对于窗口元素二次遍历寻找最大值，时间复杂度为O(nk)， 超时。这个办法的问题其实是，在每次移动窗口时，我们只是移除了一个元素，并新增加一个元素，但是却需要二次遍历当前的窗口，即上一个求出的最大值无法给下次寻找最大值带来任何便利。

一个优化思路是cache住上个窗口的最大值相关的部分信息，带入下一个窗口，这里使用一个定制的单调递减队列实现，具体的实现如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        MyQueue queue = new MyQueue();

        List<Integer> ans = new LinkedList<>();


        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        ans.add(queue.peek());


        for (int i = k; i < nums.length; i++) {
            
            queue.add(nums[i]);
            queue.poll(nums[i - k]);
            ans.add(queue.peek());

        }

        return ans.stream().mapToInt(i -> i).toArray();
    }

    // customize a monotonically decreasing queue
    class MyQueue {
        Deque<Integer> deque = new LinkedList<>();

        // if the slide window rule out our head element
        // then pop it, else pop nothing, as we do not cache
        // them actaully
        public void poll (int val) {
            if ( val == deque.peek()) {
                deque.poll();
            }
        }

        // for every new added element, try to add them into the queue
        // if they are less then any elements, just add it at the last
        // else delete those less than it, as they are meanningless now

        public void add (int val) {
            // note here, we need to remain the same large element within the queue
            // if here we use val >= deque.last, we would rule out the same large element
            while (!deque.isEmpty() && val > deque.peekLast()) {
                deque.removeLast();
            }
            deque.addLast(val);
        }

        // since we maintain such a queue that the head element is always our
        // maximum value in this window
        public int peek() {
            return deque.peek();
        }

    }
}

LeetCode 347.前k个高频元素

这道题目的难度不高，首先对数组内出现的数计算频次，使用hashmap，然后对entry按照value排序，然后输出，

看了下题解，很多都是用优先队列，小顶堆来做，暂时不是很熟悉。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        // step 1 : count the frequence of each element
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                map.put(nums[i], map.get(nums[i]) + 1);
            }else {
                map.put(nums[i], 1);
            }
        }

        // step 2 : sort the frequences
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
      	// can use lambda expression to simplify the declaration of the comparator
      	// list.sort((o1,o2)-> (- o1.getValue().compareTo(o2.getValue())));
        list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
                // the defult order is natrual order i.e. increasing order
                return -o1.getValue().compareTo(o2.getValue());
            }
        });

        // steo 3 : output the ans
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = list.get(i).getKey();
        }

        return ans;
    }
}

另外一种思路是使用小顶堆，即优先队列进行排序和输出操作，注意小顶堆中，最小的元素处于head节点，然后从后向前依次弹出。

public int[] topKFrequent2(int[] nums, int k) {

    // step 1 : count the frequence of each element
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }

    // step 2 : sort the frequences
    PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
    for (Map.entry<Integer, Integer> entry : map.entrySet()) {
        if (pq.size() < k) {
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }else {
            if (entry.getValue() > pq.peek()[1]){
                pq.poll();
                pq.add(entry);
            }
        }
    }

    // steo 3 : output the ans
    int[] ans = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        ans[i] = pq.poll()[0];
    }

    return ans;
}