代码随想录算法训练营day12 | leetcode 239. 滑动窗口最大值 347.前 K 个高频元素

基础知识

ArrayDeque deque = new ArrayDeque();
/*
 offerFirst(E e) 在数组前面添加元素，并返回是否添加成功
 offerLast(E e) 在数组后天添加元素，并返回是否添加成功
 pollFirst()删除第一个元素，并返回删除元素的值，如果元素为null，将返回null
 pollLast()删除最后一个元素，并返回删除元素的值，如果为null，将返回null
 getFirst() 获取第一个元素,如果没有将抛出异常
 getLast() 获取最后一个元素，如果没有将抛出异常
 toArray() 转成数组
 contains(Object o) 判断队列中是否存在该元素
 size() 获取队列中元素个数
 isEmpty() 判断队列是否为空
 
 队列操作 offer poll peek
 栈操作   push pop peek
*/
PriorityQueue
PriorityQueue<Object> pq = new PriorityQueue<>((o1, o2)->o1.xxx-o1.xxx);
// offer poll size toArray contains peek

//  Map遍历 效率更高
for (Map.Entry<String, String> entry : myMap.entrySet()) {
    System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}

LeetCode 239. 滑动窗口最大值

分析1.0

遍历数组添加新元素时，要维护一个队列，保证队列元素递减-单调递减队列

失误

不要想着把窗口中的元素全部放进队列再去找最大值

分析2.0

首先要将前k个元素按照push原则入队，之后取队首元素
pop(value)：如果窗口移除的元素value等于单调队列的出口元素（使用索引），那么队列弹出元素，否则不用任何操作
push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

这个要在容器的两头操作，没搞清楚数据结构，用普通队列操作实在是...欲哭无泪，内心愤怒值+++++++++

class Solution {

    ArrayDeque<Integer> queue = new ArrayDeque();

    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length - k + 1;
        int[] res = new int[len];
        for(int i = 0; i < k; i++){
            // queue不为空 而且首元素小于当前元素时
            while(!queue.isEmpty() && nums[queue.peek()] <= nums[i]){
                queue.poll();
            }
            while(!queue.isEmpty() && nums[queue.getLast()] <= nums[i]){
                queue.pollLast();
            }
            queue.offer(i);
        }// 前k个元素索引入队
        // 后nums.length - k 个元素入队
        int inIndex = k, outIndex = 0, index = 0;
        res[index++] = nums[queue.peek()];
        while(index < len){
            addElem(nums, inIndex++, outIndex++);
            res[index++] = nums[queue.peek()];
        }
        return res;
    }
    public void addElem(int[] nums, int inIndex, int outIndex){
        // 要出栈的元素是队首元素的话-通过数组索引锁定
        if(!queue.isEmpty() && queue.peek() == outIndex){
            queue.poll();
        }
        while(!queue.isEmpty() && nums[queue.getLast()] <= nums[inIndex]){
            queue.pollLast();
        }
        queue.offer(inIndex);
    }
}

LeetCode 347.前 K 个高频元素

分析1.0

Map<元素value，出现频率> ，按照频率降序排序，输出前k个key 或者是在每次遍历数组修改map时，维护map顺序，

维护Map顺序考虑工具堆或者自己实现算法

class Solution {
    //解法1：基于大顶堆实现
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){//大顶堆需要对所有元素进行排序
            pq.add(new int[]{entry.getKey(),entry.getValue()});
        }
        int[] ans = new int[k];
        for(int i=0;i<k;i++){//依次从队头弹出k个,就是出现频率前k高的元素
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}