【leetcode】滑动窗口最大值

【leetcode】滑动窗口最大值

题目：

给定一个数组 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

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

思路：

使用双向队列，在遇到新的数的时候，将新的数和双向队列的末尾进行比较，如果末尾的数比新数小，则把末尾的数扔掉，直到该队列的末尾数比新数大或者队列为空的时候才停止。这样，我们可以保证队列里的元素是重头到位的降序。由于队列中只有窗口里的数，就是窗口里的第一大数，第二大数，第三数...。

如何保持队列呢。每当滑动窗口的k已满，想要新进来一个数，就需要把滑动窗口最左边的数移出队列，添加新的数。

我们在添加新的数的时候，就已经移出了一些数，这样队列头部的数不一定是窗口最左边的数。技巧：我们队列中只存储那个数在原数组的下标。这样可以判断该数是否为最滑动窗口的最左边的数。

为什么这个解法的时间复杂度是O(N)呢。因为每个元素在双端队列里有且仅存在过一次。即最多被操作两次，一次是加入该队列的时候，一次是因为后面有更大的数而被移除队列的时候

java代码：

class Solution {
   public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length==0) {
            return null;
        }
 
        ArrayDeque<Integer> adq = new ArrayDeque<Integer>(k);
        int[] res = new int[nums.length + 1 - k];//获得该nums数组滑动窗口的个数
        for(int i = 0; i < nums.length; i++){
            //每当新数进来，如果发现队列的头部的数的下标是窗口最左边的下标，则移出队列
            if(!adq.isEmpty() && adq.peekFirst() == i - k)
                adq.removeFirst();
            //把队列尾部的数和新数一一比较，比新数小的都移出队列，直到该队列的末尾数比新数大或者队列为空的时候才停止，保证队列是降序的
            while(!adq.isEmpty() && nums[adq.peekLast()] < nums[i])
                adq.removeLast();
            //从尾部加入新的数
            adq.offerLast(i);
            //队列头部就是该窗口最大的数
            if(i >= k -1)//i < k - 1时，滑动窗口才有最大值
                res[i + 1 -k] = nums[adq.peek()];
 
        }
        return res;
    }
}