用单调队列解决滑动窗口最大值

题目链接-来源：力扣（LeetCode）

给定一个数组 nums 和滑动窗口的大小 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有更大的数字加入窗口，则该数称为新的「最大值」
  • 2这个数字被移出窗口
    这个特性非常类似「双端队列」，但是我们需要在其基础上添加一些特性。
    从 条件2 可知，我们的队列如果要很方便地找到「最大值」，必须将最大值安排在队列的一端，我们称为前端，并且队列从前端单调递减，这样我们才能保证移出「最大值」以后，前端元素仍是其余元素的「最大值」。而新元素必须从后端加入，两者才能互不影响。
    从 条件1 可知，我们加入的元素如果大于后端元素，因为它的移出时间一定晚于已有的元素，所以在其之前存在的所有较小都对此后队列的「最大值」没有任何影响，因此我们可以将这些较小的旧元素放心地移出队列；这样一来，我们的队列仍然保持了单调递减的性质。
    在窗口更新时，我们只需考虑维护该双端队列两端，前端维护「最大值」，我们判断移出的元素是否与之相等，若相等则移出该最大值；后端维护「最新值」，我们比较新元素与后端当前元素大小，移出后端元素直到新元素小于等于后端元素。
    这样的双端队列实现称为「单调队列」。
    时间复杂度：O(n)
    空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return new int[0];
        }
        int len = n - k + 1;
        int[] ret = new int[len];
        Deque<Integer> dq = new LinkedList<>();
        for (int i = 0 ; i < k; i++) {
            int vi = nums[i];
            while (!dq.isEmpty() && dq.peekLast() < vi) {
                dq.pollLast();
            }
            dq.offerLast(vi);
        }
        ret[0] = dq.peekFirst();
        
        for (int i = 1; i < len; i++) {
            if (nums[i - 1] == dq.peekFirst()) {
                dq.pollFirst();
            }
            int vi = nums[i + k - 1];
            while (!dq.isEmpty() && dq.peekLast() < vi) {
                dq.pollLast();
            }
            dq.offerLast(vi);
            ret[i] = dq.peekFirst();
        }
        
        return ret;
    }
}