【单调队列】滑动窗口最大值
题目要求我们求出固定长度为 k 的滑动窗口从左向右滑动过程中，每个位置对应的窗口最大值。例如：
▼text复制代码滑动窗口的位置 | 最大值 ------------------------------------- [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
接下来，如何求出窗口内的最大值呢？一个直观的想法是：每次都遍历窗口内的所有元素，找出最大值。
然而，这种做法效率较低。因为窗口每次向右移动一格时，只会有一个元素移出窗口、一个新元素进入窗口，有不少旧元素是重叠的。每次重新遍历整个窗口，都会重复计算这些重叠元素。
因此，这种做法的时间复杂度为 $O(nk)$，其中，$n$ 是数组 nums 的长度，$k$ 是滑动窗口的长度。
那么，我们能否在窗口滑动的过程中，维护一些有用的信息，使得我们不必每次都重新遍历整个窗口？
一个自然的想法是，我们可以尝试记录上一个窗口的最大值。然而，当上一个窗口的最大值离开窗口时，我们仍然需要重新遍历窗口内的剩余元素，才能找到新的最大值。因此，仅仅记录最大值是不够的。
那么，能否在记录最大值的同时，也记录其他可能成为最大值的元素？这样，当最大值离开窗口时，我们就有机会直接从这些元素中找到新的最大值，而不必重新遍历整个窗口。
不过，窗口内的所有元素都有必要记录下来吗？
我们可以先考虑这样一种情况：如果一个新进入窗口的元素，它比窗口中某个先进入的元素更大，那么后者还有可能成为窗口的最大值吗？
举个例子，假设窗口中有一个元素 3，现在又有一个更大的元素 5 进入窗口。由于窗口始终向右滑动，后进入的 5 一定比先进入的 3 更晚离开窗口。既然 5 更大，那么 3 就不可能再成为窗口的最大值，可以将其排除。
更进一步，如果新进入窗口的元素比前面多个元素都大，那么这些元素也都可以排除。因为它们比新元素小，并且会比新元素更早离开窗口，因此不可能再成为窗口的最大值。
这样，我们就不必记录窗口内的所有元素，只需要保留那些仍有可能成为最大值的元素。
既然只需要保留候选元素，我们应该按照什么顺序组织它们，才能快速找到最大值？
我们可以让候选元素按照从大到小的顺序排列。这样，每次只需要查看第一个元素，就能得到当前窗口的最大值。
那么，当一个新元素进入窗口时，应该如何维护候选元素的排列顺序呢？
我们可以从候选元素的末尾开始，将新元素与末尾元素进行比较。如果新元素更大，就移除末尾元素，并继续比较；直到末尾元素不再比新元素小，或者候选元素为空，再将新元素加入末尾。
例如，已有候选元素 6、4、3、2，现在新进入一个元素 5。由于 5 比 4、3、2 都大，因此这三个元素都可以排除。将 5 加入后，候选元素变为 6、5，仍然保持从大到小的顺序。
接下来，还需要考虑窗口向右移动时，如何处理离开窗口的元素。
我们前面已经规定，候选元素从大到小排列。因此，当窗口最左边的元素离开时，我们只需要判断它是不是候选集合中的最大值。如果是，就移除候选集合中的第一个元素；否则，不需要处理。
观察上述操作，我们需要从末尾移除元素、从末尾添加元素、从开头移除元素，同时还需要快速访问第一个元素。因此，可以使用**双端队列（deque）**来存储候选元素。
由于我们始终维护候选元素从大到小的排列顺序，因此这个队列具有单调性。这样的队列称为单调队列（monotonic queue）。
在本题中，我们维护的是一个单调递减队列：队列中的元素从队首到队尾单调递减，队头元素就是当前候选元素中的最大值。
基于这一思路，我们可以写出如下代码：
▼java复制代码public int[] maxSlidingWindow(int[] nums, int k) { List<Integer> res = new ArrayList<>(); // 窗口表示为左闭右开区间 [l, r) int l = 0, r = 0; Deque<Integer> q = new ArrayDeque<>(); while (r < nums.length) { int cur = nums[r++]; // 新元素进入时，从队尾移除比它小的候选元素，再将新元素加入队尾。 while (!q.isEmpty() && cur > q.peekLast()) { q.removeLast(); } q.addLast(cur); if (r - l == k) { // 窗口形成后，记录队头元素作为当前窗口的最大值。 res.add(q.peekFirst()); // 移除窗口最左侧的元素；如果它等于队头元素，则同时移除队头。 int removed = nums[l++]; if (removed == q.peekFirst()) { q.removeFirst(); } } } return res.stream() .mapToInt(Integer::intValue) .toArray(); }
复杂度分析：
- 时间复杂度为 $O(n)$：虽然代码中有嵌套的
while循环，但每个元素最多入队一次，也最多从队尾或队头移除一次。因此，所有元素在队列上的操作总次数为 (O(n))，整体时间复杂度为 (O(n))。 - 空间复杂度为 $O(k)$：不计存储结果数组
res所需的空间，额外空间主要由双端队列q占用。队列中最多保存当前窗口内的候选元素，因此最多存储 (k) 个元素，空间复杂度为 (O(k))。
