代码随想录算法训练营第十一天 | LeetCode 239(滑动窗口最大值) LeetCode 347(前K个高频元素)

239: 滑动窗口最大值

LeetCode 239(滑动窗口最大值)

import java.util.Deque;
import java.util.LinkedList;
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < k; i++){
            while(!queue.isEmpty() && queue.peekLast() < nums[i]){
                queue.pollLast();
            }
            queue.offerLast(nums[i]);
        }
        res[index++] = queue.peekFirst();
        for(int i = k; i < nums.length; i++){
            //看要不要出栈
            if(queue.peekFirst() == nums[i - k]){
                queue.pollFirst();
            }
            //看要不要进栈
            while(!queue.isEmpty() && queue.peekLast() < nums[i]){
                queue.pollLast();
            }
            queue.offerLast(nums[i]);
            res[index++] = queue.peekFirst();
        }
        return res;
    }
}

347: 前K个高频元素

LeetCode 347(前K个高频元素)

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Set;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(
            (x,y) -> y[1] - x[1]
        );
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        Set<Integer> keySet = map.keySet();
        for(int i : keySet) {
            queue.offer(new int[]{i,map.get(i)});
        }
        int[] res = new int[k];
        for(int i = 0;i < k;i++){
            res[i] = queue.poll()[0];
        }
        return res; 
    }
}