问题描述

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

依次返回数组中窗口长度为k的最大值。

举个例子：

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[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

Thanks

米开：LeetCode 239. Sliding Window Maximum{:target=”_blank”}
tt2767{:target=”_blank”}
flyingpenguin{:target=”_blank”}

此题可以使用单调队列思想。

先来看一种容易理解的方式，队列里面存的是值。

首先，针对于此题，我们需要让单调队列具有递减的特性。

然后，我们需要提前处理开始的k个元素，为后面的滑窗做准备。

接着，使用两个索引，i代表窗的左侧，初始值为1，

j代表窗的右侧，初始值为k，然后依次遍历并递增。

需要注意，什么时候将队列中的过期最大值删除？

我们可以借助左边的索引值，如果nums[i - 1] == queue.peek()

那么，就说明该最大值已过期。

来看下实现：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        List<Integer> ans = new LinkedList<>();
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i < k; i++){
            int cur = nums[i];
            while (!queue.isEmpty() && queue.peekLast() < cur){
                queue.pollLast();
            }
            queue.offerLast(cur);
        }

        ans.add(queue.peek());
        int n = nums.length;
        for (int i = 1, j = k; i < n && j < n; i++, j++){
            if (!queue.isEmpty() && queue.peekFirst() == nums[i - 1]){
                queue.pollFirst();
            }
            int cur = nums[j];
            while (!queue.isEmpty() && queue.peekLast() < cur){
                queue.pollLast();
            }
            queue.offerLast(cur);
            ans.add(queue.peek());
        }
        return ans.stream().mapToInt(i -> i).toArray();
    }
}

第二种方式比较优雅，队列中存的是索引

来看下实现：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        // Store indices.
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        int n = nums.length;
        int[] ans = new int[n - k + 1]; 

        for (int i = 0; i < n; i++){
            while (queue.size() > 0 && queue.peek() < i - k + 1){
                queue.poll();
            }
            while (queue.size() > 0 && nums[queue.peekLast()] < nums[i]){
                queue.pollLast();
            }
            queue.offer(i);
            if (i >= k - 1){
                ans[i - k + 1] = nums[queue.peek()];
            }
        }
        return ans;
    }
}

Enjoy it !