双端队列题解
239. 滑动窗口最大值
方法一：暴力法
该题最直接的解法，直接遍历每个滑动窗口，找到每个窗口的最大值即可。一共会有 N - k + 1 个滑动窗口，每个滑动窗口有 k 个元素，所以时间复杂度为 O(Nk)，表现较差。
方法二：双端队列
这里采用 以双向链表实现的 LinkedList 作为双端队列。
算法
- 遍历整个数组。
- 把当前元素的索引添加到双端队列中，在添加之前首先清理双端队列：
- 遍历当前双端队列。
- 移除比当前元素小的所有元素，它们不可能是最大的，保证双端队列队首到队尾按从大到小的顺序排列，这样保证了队首永远是当前窗口最大的。
- 如果队首的索引超出了窗口，则移除队首。
- 将对首元素添加到输出数组中。
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0) return new int[0];
LinkedList<Integer> qmax = new LinkedList<>();
int[] result = new int[nums.length - k + 1];
int index = 0;
for(int i = 0; i < nums.length; i++) {
// 遍历双端队列，将比当前元素小的所有元素移除
while(!qmax.isEmpty() && nums[i] >= nums[qmax.peekLast()]) {
qmax.pollLast();
}
// 将当前元素的索引添加到队列
qmax.addLast(i);
// 如果队首的索引超出了窗口，移除
if(qmax.peekFirst() == i - k) {
qmax.pollFirst();
}
// 第一个窗口生成，构建输出结果
if(i >= k - 1) {
result[index++] = nums[qmax.peekFirst()];
}
}
return result;
}
复杂度
- 时间复杂度：O(N)，每个元素被处理两次，其索引被添加到双端队列，和被双端队列删除。
- 空间复杂度：O(N)，输出数组使用了 O(N - k + 1) ，双端队列使用了 O(k)。
