算法训练营Day13(栈队列)

发布时间:2023年12月17日

239.?滑动窗口最大值?(一刷至少需要理解思路

239. 滑动窗口最大值 - 力扣(LeetCode)

这道题用到了双端队列

既可以做队列也可以做栈

队列相关操作

poll:弹出队头元素

peek:查看队头

add:队尾添加元素

removeLast :删除队尾元素

解题思路:

23516

单调队列,push操作的时候,val和最后一个元素比,大的话,就循环移除last

比如

2

push3 >2? ? 3

push5>3? ?5

push1<5? 51

push6>1? 移除1? ?6>5移除6

get操作:

刚才的push逻辑可以看出,get的时候一定是最大值。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        int [] res = new int[nums.length-k+1];
        int index = 0;

        MyQueue queue = new MyQueue();


        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        res[index++] = queue.peek();
        
        // 1  2  3  4
        for (int i = k; i < nums.length; i++) {
            queue.poll(nums[i-k]);
            queue.add(nums[i]);
            res[index++] = queue.peek();
        }

        return res;
    }
}

class MyQueue{

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

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

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

    int peek(){
        return deque.peek();
    }
}

347.前?K?个高频元素? (一刷至少需要理解思路)

347. 前 K 个高频元素 - 力扣(LeetCode)

这道题并不难,就是理解好什么是大顶堆,建议自己去手写大顶堆,堆排序,topK问题这些基础的操作还是要会的,java的优先级队列好像不能指定堆的大小,所以需要在循环里指定一下。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 数组的0是数组,1是频率
        PriorityQueue<int []> queue = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        for( Map.Entry<Integer, Integer> x: map.entrySet()){
            Integer key = x.getKey();
            Integer value = x.getValue();
            queue.add(new int[]{key,value});
            //保留前k个频率最高
            if(queue.size()>k){
                queue.poll();
            }
        }

        int [] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }
}

总结

卡哥总结

这是卡哥总结的,我总结就是注意下面这些地方

对于java,Deque就是卡哥说的双端队列,这一个队列就可以做栈和队列两个结构的操作,还很方便,头尾都能操作,就很方便写题以及项目中相关操作。

对于栈,注意栈的结构做一下巧妙的消除,可以回顾前面的题来理解这个思想。

对于队列的话,好像没什么需要注意的,就是注意滑动窗口这个的思想以及大顶堆这个数据结构

在大数据领域,堆还是很好的,因为比如100亿数据想要找到TOPK的值,对于绝大多数数据结构基本内存扛不住的,但是大顶堆、小顶堆只需要k个空间就可以了。java语言可以参考优先级队列直接调用,做题的时候不用手敲了我认为。联系的时候可以敲一下。

日后补充

另外,对于程序,网页,怎么用到栈这样的结构的,java的调用栈,一层一层弹入,返回上一级,弹出,可以做一下这道题。

71. 简化路径

力扣71题,刷题的时候可以看。

文章来源:https://blog.csdn.net/weixin_65728526/article/details/134925923
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。