239.滑动窗口最大值

文章：7. 滑动窗口最大值

题目：239. 滑动窗口最大值

视频：单调队列正式登场！| LeetCode：239. 滑动窗口最大值_哔哩哔哩_bilibili

难点在于：如何求滑动窗口里面的最大值。

【思路】

滑动窗口很像一个队列。

单调队列。维护队列里面的元素单调递增或单调递减。

因此我们采用Deque进行处理：著需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

1.pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。

2.push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到（while）push元素的数值小于等于队列入口元素的数值为止。

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

pop()

push()

getMaxValue()

Java实现

class Solution {

    
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 1)return nums;
        int len = nums.length-k+1;
        int[] res = new int[len];
        int num = 0;
        MyDeque deque = new MyDeque();
        for(int i = 0;i<k;i++){
            deque.add(nums[i]);
        }
        res[num++] = deque.peek();
        for(int i = k;i<nums.length;i++){
            //滑动窗口移除最前面的元素，移除是判断该元素是否有放入队列
            deque.poll(nums[i-k]);
            //滑动窗口加入最后面的元素
            deque.add(nums[i]);
            res[num++] = deque.peek();
        }
        return res;

    }
}

class MyDeque{
    Deque<Integer> deque = new LinkedList<>();
    void poll(int val){
        if(!deque.isEmpty() && val == deque.peek()){
            deque.poll();
        }
    }

    void add(int val){
        //弹出所有比val小的数值，保持队列单调递减
        while(!deque.isEmpty() && val > deque.getLast()){
            deque.removeLast();
        }
        deque.add(val);
    }

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

Go实现

type MyQueue struct{
    queue []int
}
func NewMyQueue()*MyQueue{
    return &MyQueue{
        queue: make([]int,0),
    }
}
func(m *MyQueue)Empty()bool{
    return len(m.queue) == 0
}
func(m *MyQueue) Front()int{
    return m.queue[0]
}
func(m *MyQueue)Back()int{
    return m.queue[len(m.queue)-1]
}
func(m *MyQueue)Push(val int){
    for !m.Empty() && val > m.Back(){
        m.queue = m.queue[:len(m.queue)-1]
    }
    m.queue = append(m.queue,val)
}
func(m *MyQueue)Pop(val int){
    if !m.Empty() && val == m.Front(){
        m.queue = m.queue[1:]
    }
}
func maxSlidingWindow(nums []int, k int) []int {
    queue := NewMyQueue()
    length := len(nums)
    res := make([]int,0)
    for i := 0 ; i < k ; i++{
        queue.Push(nums[i])
    }
    res = append(res,queue.Front())
    for i := k ; i < length;i++{
        queue.Pop(nums[i-k])
        queue.Push(nums[i])
        res = append(res,queue.Front())
    }
    return res
}

347.前k个高频元素

文章：8. 前K个高频元素

题目：347. 前 K 个高频元素

视频：优先级队列正式登场！大顶堆、小顶堆该怎么用？| LeetCode：347.前 K 个高频元素_哔哩哔哩_bilibili

给定一个数组，求出这个数组中的每一个元素出现的频率，然后对频率找前k个高频的元素，放到数组中返回。

【思路】

1.如何求每个元素的频率 ==>使用map进行统计

2.如何对每个元素的频率进行排序 ==>使用一种容器适配器：优先级队列（披着队列外衣的堆）

3.求前k个高频的元素

堆是一颗完全二叉树，数中每个结点的值都不小于（或不大于）其左右孩子的值。

大顶堆、小顶堆：擅长在一个很大的数据集里面求前k个高频的或低频的结果的操作

底层实现是二叉树。父节点永远比左右节点要大，为大顶堆；比左右节点小即为小顶堆。

用堆维持k个元素。堆里面遍历完map里面所有的元素之后，对于里面的k个元素，就相等于维护了我们想要求的前k个高频元素。

使用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

Java实现

感觉是api的胜利（bushi）

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer>map = new HashMap<>();
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        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(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for(int i = k-1 ; i>= 0;i--){
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

Go实现

老实说，没看懂答案

//小顶堆
func topKFrequent(nums []int, k int) []int {
    map_num := map[int]int{}
    for _,item :=range nums{
        map_num[item]++
    }
    h := &IHeap{}
    heap.Init(h)
    for key,value := range map_num{
        heap.Push(h,[2]int{key,value})
        if h.Len()>k{
            heap.Pop(h)
        }
    } 
    res := make([]int,k)
    for i:=0;i<k;i++{
        res[k-i-1] = heap.Pop(h).([2]int)[0]
    }
    return res 
}

type IHeap[][2]int

func(h IHeap)Len()int{
    return len(h)
}

func(h IHeap)Less(i,j int) bool{
    return h[i][1] < h[j][1]
}

func(h IHeap)Swap(i,j int){
    h[i],h[j] = h[j],h[i]
}

func(h *IHeap)Push(x interface{}){
    *h = append(*h,x.([2]int))
}

func(h *IHeap)Pop()interface{}{
    old:= *h
    n := len(old)
    x := old[n-1]
    *h = old[0:n-1]
    return x
}

方法二：排序

func topKFrequent(nums []int, k int) []int {
    ans :=[]int{}
    map_num := map[int]int{}
    for _,item := range nums{
        map_num[item]++
    }
    for key,_ := range map_num{
        ans = append(ans,key)
    }
    sort.Slice(ans,func(a,b int)bool{
        return map_num[ans[a]]>map_num[ans[b]]
    })
    return ans[:k]
}

栈与队列总结

栈与队列的理论基础

可以出一道面试题：栈里面的元素在内存中是连续分布的么？

这个问题有两个陷阱：

陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？
答案是：不连续的，下文也会提到deque。

了解了栈与队列基础之后，那么可以用栈与队列：栈实现队列 (opens new window)和栈与队列：队列实现栈 (opens new window)来练习一下栈与队列的基本操作。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外）重新添加到队列尾部，此时再去弹出元素就是栈的顺序了

栈经典题目

栈在系统中的应用

如果还记得编译原理的话，编译器在词法分析的过程中处理括号、花括号等这个符号的逻辑，就是使用了栈这种数据结构。

再举个例子，linux系统中，cd这个进入目录的命令我们应该再熟悉不过了。

1	cd a/b/c/../../

这个命令最后进入a目录，系统是如何知道进入了a目录呢，这就是栈的应用。这在leetcode上也是一道题目，编号：71. 简化路径，大家有空可以做一下。

递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

括号匹配问题

使用栈解决的经典问题。

思路：需要分析三种情况（多余、类型不匹配、顺序不对）

一个小技巧：在匹配左括号的时候，右括号先入栈，只需要匹配当前元素和栈顶元素是否相等即可。

字符串去重问题

思路：把字符串顺序放到一个栈中，如果相同的话栈就弹出，这样最后栈里剩下的元素就是相邻不相同的元素了。

逆波兰表达式

思路：当遇到四则运算符号时，就对栈内的元素进行四则运算后压入栈，最后返回栈顶元素即可。

需要注意减号和除号前后元素的运算顺序

队列的经典题目

滑动窗口最大值问题

思路：单调队列。我们只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值由大到小。

需要注意单调队列的写法不唯一，不同场景写法不同。

求前k个高频元素

思路：使用优先级队列对部分频率进行排序（大顶堆和小顶堆）。

总结

队列的题目还没有完全理解，复盘的时候需要着重复习！

在此感谢卡尔劳斯的知识分享！:)