滑动窗口的最大值。提议是给一个数组和一个滑动窗口的大小K，请返回一个数组，存储这个窗口遍历input数组的时候每个窗口的最大值。例子，
Example:
Input: nums =[1,3,-1,-3,5,3,6,7], and k = 3 Output:[3,3,5,5,6,7] Explanation:Window position Max --------------- ----- [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
思路是用到单调栈，此处引用了LC中文网的一个discussion。这个题还有priority queue的做法但是不是最优解，此处就不过多解释了。
算法非常直截了当：
处理前 k 个元素，初始化双向队列。
遍历整个数组。在每一步 :
清理双向队列 :
- 只保留当前滑动窗口中有的元素的索引。
- 移除比当前元素小的所有元素，它们不可能是最大的。
将当前元素添加到双向队列中。
将 deque[0] 添加到输出中。
返回输出数组。作者：LeetCode
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetcode-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
时间O(n)
空间O(n)
Java实现
1 class Solution {
2 public int[] maxSlidingWindow(int[] nums, int k) {
3 // corner case
4 if (nums == null || nums.length == 0)
5 return new int[0];
6 // normal case
7 int[] res = new int[nums.length + 1 - k];
8 Deque<Integer> queue = new LinkedList<>();
9 for (int i = 0; i < nums.length; i++) {
10 if (!queue.isEmpty() && queue.peekFirst() == i - k) {
11 queue.poll();
12 }
13 while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
14 queue.removeLast();
15 }
16 queue.offerLast(i);
17 if ((i + 1) >= k) {
18 res[i + 1 - k] = nums[queue.peek()];
19 }
20 }
21 return res;
22 }
23 }
JS实现
1 /**
2 * @param {number[]} nums
3 * @param {number} k
4 * @return {number[]}
5 */
6 var maxSlidingWindow = function (nums, k) {
7 const res = [];
8 const q = [];
9 for (let i = 0; i < nums.length; i++) {
10 while (q.length - 1 >= 0 && nums[i] > q[q.length - 1]) {
11 q.pop();
12 }
13 q.push(nums[i]);
14 // When i + 1 - k >= 0, the window is fully overlapping nums
15 const j = i + 1 - k;
16 if (j >= 0) {
17 res.push(q[0]);
18 // If the biggest element in q is about to exit window, remove it from q
19 if (nums[j] === q[0]) {
20 q.shift();
21 }
22 }
23 }
24 return res;
25 };