代码随想录算法训练营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;

    }

}

总结

在进行栈、队列等容器操作时，要先判断容器是否为空
循环首先要确认终止条件、避免常见的ArrayOutOfIndex错误
PriorityQueue 实现自定义比较器，构造器参数不能为Map

常用变量名增量更新

size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch

巴特西

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

基础知识

LeetCode 239. 滑动窗口最大值

LeetCode 347.前 K 个高频元素

总结

常用变量名增量更新

最新文章

热门文章