X

LEETCODE 239. Sliding Window Maximum 解题思路分析

题目大意:

滑动窗口最大值

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 
 滑动窗口的位置                最大值
 ---------------               -----
 [1  3  -1] -3  5  3  6  7       3
  1 [3  -1  -3] 5  3  6  7       3
  1  3 [-1  -3  5] 3  6  7       5
  1  3  -1 [-3  5  3] 6  7       5
  1  3  -1  -3 [5  3  6] 7       6
  1  3  -1  -3  5 [3  6  7]      7

提示:

你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。

进阶:

你能在线性时间复杂度内解决此题吗?


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=239

解题思路分析:

本题是一道高频面试题,这里介绍二种解题思路。时间复杂度分别是O(nlogn)以及O(n)

解法一:二分查找,时间复杂度 O(nlogn)

按顺序遍历一遍数组,循环时,将当前元素插入到一个新建List集合中,插入时采用二分查找方式插入,以保证List内数字是有小到大排序。当循环下标移动到数组的k-1位置时,也就是List的大小等于k时,说明当前区间长度已经满足k,我们需要在当前区间找到一个最大值加入返回结果,由于List已经排好序,因此当前区间内的最大值应该是List中的最后一个元素。继续循环到数组的下一位,此时下标k-i位上的数字将会被移除出k区间,我们应该从List中删除数组中对应的k-i位上的数字,然后再使用二分查找方式将第i位的数字插入到List中,以此类推,直到循环完数组中所有数字。

本解法循环数组的时间复杂度是数组长度n,每次向List中插入数据的时间花费logn,因此总的时间复杂度为 O(nlogn) 。

实现代码:

public int[] maxSlidingWindow(int[] nums, int k) {
    // 如果数组为空,直接返回空
    if(nums.length==0) return new int[0];
    // 排序用的List
    List<Integer> list = new ArrayList<>();
    // 返回结果
    int[] res = new int[nums.length-k+1];
    // 循环数组中每一个数字
    for(int i=0;i<nums.length;i++){
        // 如果List的大小等于k,说明当前元素插入之前k区间内的元素已满,
        // 需要删除区间最左边的元素,即下标为i-k位的数字
        if(list.size()==k){
            list.remove(Integer.valueOf(nums[i-k]));    
        }
        // 当前进入k区间的元素
        int in = nums[i];
        // 利用二分查找,找到当前元素插入位置,保证list升序
        int left=0, right=list.size()-1;
        while(left<=right){
            int mid=(left+right)/2;
            int midNum=list.get(mid);
            if(in==midNum){
                left=mid;
                break;
            }
            if(in>midNum) left=mid+1;
            else right=mid-1;
        }
        // 将当前元素插入到list中
        list.add(left, in);
        // 如果当前区间长度等于k,找到一个最大值存入返回结果
        if(list.size()==k) res[i-k+1]=list.get(k-1);
    }
    return res;
}

本解法执行时间为32ms。

Runtime: 32 ms, faster than 26.92% of Java online submissions for Sliding Window Maximum.

Memory Usage: 41.3 MB, less than 81.25% of Java online submissions for Sliding Window Maximum.


解法二:Deque,时间复杂度为O(n)

之前的文章并没有涉及过Deque的讲解,这里重点分享一下,Deque解法也是本题官方给出的最优解法,面试时使用这种解法也会令你的面试官对你刮目相看。

之前的文章多次讲过堆栈Queue,它是广度优先搜索bfs算法的核心。堆栈Queue是基于先进先出的原则,而且是单向的,也就是说,我们只能向队伍的尾部插入数据,然后从头部取出数据,类似于人群排队。而Deque也是一种Queue,被称为双向堆栈,我们不仅可以向队尾插入数据,也允许向头部添加数据,同理取数据时,头尾两侧的数据均可以取出。

回到本题,通过题目中给出的提示信息来分析,在Deque中仅存储有价值的数据,没用的全部移除掉。那么我们需要考虑什么数据是没用的?举个例子来说明一下,还是使用题目中的例子:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

我们还是需要按顺序循环一遍数组元素,先将1放入到 Deque 的尾部,此时 Deque 中只有数字1。接下来需要将3放入堆栈尾部,在放入之前,先从 Deque 尾部向前查看已存在的数字,数字1要小于当前的3,我们可以认定数字1就是没用的那个元素!原因分析:因为当前3大于1,在向右滑动k区间的过程中,当3被移除出区间之前,1永远不会是最大的那个值,并且在3被移除出区间的时间点,数字1已经先一步被移除出区间了,因此无论如何1也不会被选作最大值,即1是无用数据。以此类推,在插入当前数字之前,Deque中所有小于当前数字的元素都是可以被删除掉的,删除这些无用数据之后,再插入当前数字即可,此时 Deque 中的数据能够保证由大到小的顺序排列(头最大,尾最小)。由此可得出区间内的最大值一定是 Deque 的头元素。

解题时,还需要注意另外一个问题,区间是有长度限制的,即题目给出的k值。在区间向右滑动的过程中,不仅要将区间右下标的值加入到区间内,还需要将区间左下标减一的值移除出区间,当Deque的头元素等于 区间左下标减一对应的数字 时,Deque的头元素需要被移除掉。

实现代码:

public int[] maxSlidingWindow(int[] nums, int k) {
    // 如果数组为空,直接返回空
    if(nums.length==0) return new int[0];
    // 返回结果
    int[] res = new int[nums.length-k+1];
    // 保存区间内数字用的Deque
    Deque<Integer> dq = new LinkedList<>();
    // 循环数组中每个数字
    for(int i=0;i<nums.length;i++){
        // 当前数字
        int num = nums[i];
        // 如果Deque元素个数大于0并且头元素等于k区间左下标减一的数
        if(dq.size()>0&&i-k>=0&&dq.peekFirst()==nums[i-k]){
            // 移除头元素
            dq.pollFirst();
        }
        // 移除无用元素
        while(dq.size()>0 && dq.peekLast()<num){
            dq.pollLast();
        }
        // 添加当前元素
        dq.offerLast(num);
        // 当前为合理区间
        if(i>=k-1){
            // 将区间内最大值加入到返回结果
            res[i-k+1]=dq.peekFirst();
        }

    }
    return res;
}

本解法执行时间为10ms。

Runtime: 10 ms, faster than 77.52% of Java online submissions for Sliding Window Maximum.

Memory Usage: 41.3 MB, less than 82.81% of Java online submissions for Sliding Window Maximum.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-239-sliding-window-maximum-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)