LeetCode：滑动窗口最大值

文章收录于LeetCode专栏
LeetCode地址

滑动窗口最大值

题目

  给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
  返回 滑动窗口中的最大值 。
  示例 1：

输入：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

  示例 2：

输入：nums = [1], k = 1
输出：[1]

双端队列

算法思路

  从题目可得，该题所指定的窗口是恒定的，同时只要进入窗口的元素比它前面的元素大，那么在它之前的元素就永远不再会成为最大值。所以根据以上两点分析可以使用一个双端队列，通过对双端队列的出队和入队操作来选择窗口中最大的元素值。所谓双端队列，其实就是队列的左右两端都可以进行入队和出队操作。
  以nums = [1,3,-1,-3,5,3,6,7]，k = 3为例，具体思路如下：
  说明：双端队列维护的是元素对应的下标

1. 初始窗口K长度的双端队列
   a. 队列为空，元素1直接从右端入队（[1]）
   b. 元素3大于队尾元素1，移除队尾元素1，然后元素3从右端入队（[3]）
   c. 元素-1小于队尾元素3，直接从右端入队（[3,-1]）
2. 移动窗口维护双端队列
   a. 判断当前移动窗口的轮次是否已经超过双端队列左端的队首元素的下标
     i. 如果超过就需要先将双端队列左端的队首元素出队
      ii. 反之跳过此步骤
   b. 循环判断当前需入队的元素是否大于等于双端队列右端的队尾元素
      i. 如果大于等于，则移除双端队列右端的队尾元素，然后再循环判断
     ii. 反之跳过此步骤
   c. 将当前需入队的元素从双端队列的右端入队
   d. 将双端队列左端队首元素输出放入返回数组

  以上便是使用双端队列解答该题的详细思路，可结合以下动图理解

编码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[nums.length - k + 1];
        for(int i=0; i<nums.length; i++){
            if(i >= k && deque.getFirst() <= i-k){
                // 如果双端队列头部元素的下标小于等于当前窗口首位元素的下标
                deque.removeFirst();
            }
            while(!deque.isEmpty() && nums[deque.getLast()] <= nums[i]){
                deque.removeLast();
            }
            deque.addLast(i);
            if(i >= k-1){
                res[i-k+1] = nums[deque.getFirst()];
            } 
        }
        return res;
    }
}

复杂度分析

  时间复杂度：O(n)，其中 n 是数组 nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。
  空间复杂度：O(n)，即为双端队列的长度大小，用于存储每次比较的数据。