class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 移除不在窗口内的元素（即索引小于 i-k+1 的元素）
if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 移除所有比当前元素小的元素，它们不可能是最大值
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// 将当前元素的索引加入到队列中
deque.offerLast(i);
// 当前索引从 i >= k-1 时，开始记录最大值
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}代码分步解释
-
初始化与边界检查：
首先，检查输入的数组是否为空或长度为零。如果是这样，直接返回一个空数组，因为没有任何滑动窗口可计算最大值。 -
创建结果数组与双端队列：
确定数组的长度，并创建一个结果数组result来存储每个滑动窗口的最大值。结果数组的长度为n - k + 1，因为这是滑动窗口在数组中滑动的次数。创建一个双端队列（Deque），用于存储滑动窗口中可能的最大值的元素的索引。双端队列允许我们在常数时间内从两端插入或删除元素。 -
遍历数组：
开始遍历数组的每一个元素。对于每个元素，我们将更新双端队列，确保队列中的元素始终是当前窗口中可能的最大值。 -
移除窗口外的元素：
检查双端队列的最前端（即第一个元素），如果它的索引已经超出了当前滑动窗口的左边界（即索引小于i - k + 1），就将它从队列中移除。这是因为该元素已经不再属于当前窗口，不可能再成为最大值。 -
保持队列的有序性：
为了确保队列中的元素按从大到小的顺序排列，我们会移除队列中所有比当前元素小的元素。因为如果当前元素比这些元素大，那么这些元素在当前窗口内或未来的窗口中都不可能成为最大值。 -
加入当前元素：
将当前元素的索引加入到双端队列的末尾。这个步骤保证了双端队列始终包含当前窗口内可能的最大值候选者。 -
记录当前窗口的最大值：
当窗口的大小达到k时，开始记录每个窗口的最大值。双端队列的第一个元素就是当前窗口的最大值，因为队列中的元素已经被排序，最大值在最前端。 -
返回结果：
完成数组遍历后，返回结果数组，其中包含了每个滑动窗口的最大值。
双端队列（Deque）基础知识
什么是双端队列？
双端队列（Deque，全称为Double-Ended Queue）是一种特殊类型的队列，它允许在队列的两端进行插入和删除操作。与普通的队列不同，双端队列在队头和队尾都可以进行元素的添加和移除操作。
双端队列的基本操作：
offerFirst(E e)和offerLast(E e)：在队列的前端或后端插入元素。pollFirst()和pollLast()：从队列的前端或后端移除并返回元素。peekFirst()和peekLast()：查看队列的前端或后端元素，但不移除它。
为什么在滑动窗口问题中使用双端队列？
1. 高效的最大值维护：双端队列允许我们高效地追踪当前滑动窗口的最大值。我们可以在 O(1) 的时间复杂度内添加、移除元素，并快速确定窗口的最大值。
2.动态管理窗口内的元素：双端队列帮助我们在滑动窗口移动时动态管理元素，使得队列中的元素始终是当前窗口内可能的最大值候选者。
在滑动窗口问题中的应用：
- 维护一个有序的候选最大值队列：在每次滑动窗口时，我们用双端队列来存储窗口内可能的最大值，并保证这些元素的顺序。
- 高效移除过期元素：当滑动窗口向右移动时，如果队列中最前端的元素已经不在当前窗口范围内，我们可以快速将其移除。
- 保持窗口内的元素降序排列：每当我们处理一个新元素时，如果发现它比队列中的一些元素大，我们就移除这些较小的元素，因为它们不再可能成为最大值。
操作示例
Deque<Integer> deque = new LinkedList<>();
// 在队列的头部添加元素
deque.offerFirst(1);
// 在队列的尾部添加元素
deque.offerLast(2);
// 查看队列的头部元素
int firstElement = deque.peekFirst(); // 返回 1
// 查看队列的尾部元素
int lastElement = deque.peekLast(); // 返回 2
// 从队列的头部移除元素
int removedFirst = deque.pollFirst(); // 返回 1，队列现在是 [2]
// 从队列的尾部移除元素
int removedLast = deque.pollLast(); // 返回 2，队列现在为空
基础队列（Queue）基础知识
什么是队列？
队列（Queue）是一种先进先出（FIFO，First-In-First-Out）的数据结构。这意味着第一个进入队列的元素将是第一个被移除的元素。可以把它想象成排队的情形，最先排队的人最先得到服务。
队列的基本操作：
offer(E e)或add(E e)：在队列的尾部添加一个元素。这相当于一个人排队进入队列。poll()或remove()：从队列的头部移除并返回第一个元素。这相当于最先排队的人被服务后离开队列。peek()或element()：查看队列头部的第一个元素，但不移除它。这相当于查看排在最前面的人是谁，但不让他离开队列。
队列的应用场景：
1.任务调度：在操作系统中，任务排队等待 CPU 处理。
2.广度优先搜索（BFS）：在图或树的遍历中，队列用于按层级顺序访问节点。
3.生产者-消费者模式：在多线程编程中，队列用于在生产者和消费者之间传递数据。
操作示例
Queue<Integer> queue = new LinkedList<>();
// 添加元素到队列的尾部
queue.offer(1);
queue.offer(2);
queue.offer(3);
// 查看队列的头部元素，但不移除
int head = queue.peek(); // 返回 1
// 移除并返回队列的头部元素
int removedElement = queue.poll(); // 返回 1，队列现在是 [2, 3]