• 0

  • 点赞

  • 收藏

聊一聊滑动窗口最大值

1个月前

前言

开篇明义,这题我做了6个小时每过一会,我就愤恨地看看它的简单标识。所以当最后肝出来的时候,就有了和大家细致地聊聊这道题的念头(这该死的虚荣心)。

但回过头来看,这道题被标榜为简单,还是实至名归的,至少从大体的思路上来说是这样。而困扰我6个小时的其实是各种边界条件和逻辑分支,这也是我在接下来的篇幅中会着重谈到的地方。好啦,滑动窗口的故事就此拉开序幕了——

一. 问题描述

image-20210302155225916

二. 思路及复杂度分析

首先分析题意,找到滑动窗口中的最大值,既然是找最值的问题,那暴力遍历就可以解决了。而要找到滑动窗口的所有最大值,无非是找arr.length-窗口大小+1个最大值,只需要两层遍历找最值就可以了,这种朴素的思路无疑可以解决问题,但多半会被判别系统以超时无情地打回。所以呢,下面的才是正戏——

考虑使用队列的知识解决,在窗口滑动的同时维护一个存储递减序列的双端队列,该队列的首部存储有窗口中的最大值,窗口滑动时的动作无非两个:删除窗口头部元素,在窗口尾部添加元素。在窗口滑动的过程中,它的位置显然有两种情况:

  1. 未形成窗口:窗口需要移动k次才可以形成窗口。刚开始时,队列为空,则将数组中的第一个值插入到队列的尾部。在插入第二个值的时候,就需要判断队列中的最大值是否需要更新,

    那如何更新呢?我们考虑两个方向:与队列首部元素比较/与队列尾部元素比较。当与队列首部元素比较时,假如要插入元素小于当前最大值,这时还无法确定该元素在队列中的具体位置。所以这个方法显然是冗余的。

    image-20210302165943424

    假如与队列尾部元素比较,如果插入值小于队列尾部值,这种情况我们喜闻乐见。如果大于队列尾部值,则删除队列尾部值,再与删除后的尾部值比较直到队列为空或者大小关系变化为止。以上都属于对队列原有值的更新,而到最后不论大小关系如何,都要将插入值插入队列尾部

  2. 已形成窗口:未形成窗口时不存在窗口已满需要删除左端元素的情况,这也是形成队列后的唯一区别。窗口在形成后只能移动arr.length-k次。在添加元素之前,需要先判断要删除的元素是否为队列中的最大值。队列中的最大值很好得到,但要删除元素的下标要如何确认呢?这里有必要画个草图——

    image-20210302171032688

    如果要删除的元素恰好等于队列最大值,那就删除队列中所有元素。之后就和未形成窗口时处理方式一致了。

    image-20210302170543483

三. 趣味图解

图片来自:https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/

Picture1.png

四.代码演示

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        //特判
        if(length==0 || k==0)
            return new int[0];
        //声明一个队列
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[length-k+1];
        //未形成窗口
        for(int i=0;i<k;i++){
            //队列为空,将其添加到队尾
            if(deque.isEmpty()){
                deque.addLast(nums[i]);
            }else{//不为空,且要添加的值大于队列尾的值,则删除队尾中所有小于要添加元素的值
                while (!deque.isEmpty() && nums[i] > deque.peekLast()){
                    deque.removeLast();
                }
                deque.addLast(nums[i]);
            }
        }
        res[0] = deque.peekFirst();
        //形成窗口
        for(int j=k;j<length;j++){
            //删除的为最大值,则删除队列中所有元素
            if (nums[j-k]==deque.peekFirst()){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && deque.peekLast() < nums[j]){
                deque.removeLast();
            }
            //添加
            deque.addLast(nums[j]);
            //填充结果集
            res[j-k+1] = deque.peekFirst();
        }
        return res;
    
    }
}
复制代码

日拱一卒,功不唐捐。

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

java

0

相关文章推荐

未登录头像

暂无评论