题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

题解一

首先来个暴力解法，遍历每一个滑窗，计算每个滑窗的最大值并保存。

下面是参考代码：

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0)
        return new int[0];
    int left = 0, right = k - 1;
    ArrayList<Integer> res = new ArrayList<>();

    while (right < nums.length) {
        int curMax = Integer.MIN_VALUE;
        for (int i = left; i <= right; i++) {
            if (nums[i] > curMax)
                curMax = nums[i];
        }
        res.add(curMax);
        left++;
        right++;
    }
    return res.stream().mapToInt(Integer::valueOf).toArray();
}

题解二

上面的思想也可以使用队列实现，利用队列的性质，可将滑动窗口看成一个队列。当窗口滑动时，前面的数字被删除，后面的数字被加入，这就符合队列先进先出的性质。

下面是参考代码：

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0)
        return new int[0];
    ArrayList<Integer> res = new ArrayList<>();
    Queue<Integer> queue = new LinkedList<>();

    for (int num : nums) {
        // 当队列的大小等于size时，计算最大值
        if (queue.size() == k) {
            int max = Integer.MIN_VALUE;
            for (int i : queue)
                if (i > max) max = i;
            res.add(max);
            queue.poll();
        }
        queue.offer(num);
    }
    int max = Integer.MIN_VALUE;
    for (int i : queue)
        if (i > max) max = i;
    res.add(max);
    return res.stream().mapToInt(Integer::valueOf).toArray();
}

题解三

但是上面两种解法都需要对于每一个滑动窗口都遍历一遍，所消耗的时间是比较大的。

我们可以考虑使用双端队列来记录数组的下标，队列头保存当前滑动窗口最大值的下标。当窗口每滑动一次：

1. 对于新增加的值，从队尾开始比较，将队列中比它小的值丢弃，然后再入队（核心步骤）。
2. 如果队首元素超出当前滑动窗口，则出队。
3. 将新增加的数组下标入队。
4. 将当前滑动窗口的最大值加入res中。

下面是参考代码：

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0)
        return new int[0];

    // 使用double-ended queue，存放有可能成为滑窗最大值的数值
    LinkedList<Integer> deque = new LinkedList<>();
    // 将结果存入res中
    ArrayList<Integer> res = new ArrayList<>();

    for (int i = 0; i < nums.length; i++) {
        // 1.对于新增加的值，从队尾开始比较，将队列中比它小的值丢弃，然后再入队（核心步骤）。
        while (!deque.isEmpty() && nums[deque.getLast()] < nums[i])
            deque.pollLast();
        // 2.如果队首元素超出当前滑动窗口，则出队。
        if (!deque.isEmpty() && i - deque.peekFirst() == k)
            deque.pollFirst();
        // 3.将新增加的数组下标入队。
        deque.addLast(i);
        // 4.将当前滑动窗口的最大值加入到res中
        if (!deque.isEmpty() && i >= k-1)
            res.add(nums[deque.peekFirst()]);
    }
    return res.stream().mapToInt(Integer::valueOf).toArray();
}