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-解题思路分析/