239. 滑动窗口的最大值

题目：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

解题思路：
这道题很容易就可以想到暴力的做法，遍历每个长度为k的子数组，然后遍历查找子数组内的最大值。但是这样做的话会导致超时。所以不能通过遍历子数组来查找子数组中的最大值。

经过分析，我们可以发现，当窗口向右移动，nums[i]进入窗口，那么窗口内所有比它小的值是不可能成为窗口内的最大值的，只有比它大的值才可能是窗口内的最大值。如果每个nums[i]进入窗口，就把窗口内比它小的数删除，那么窗口内剩余的值全是比它大的，也就是呈现一个单调递减的序列，那么自然该序列的第一个元素就是要找的最大值。

同时，如果窗口长度超过了k，就要把窗口第一个元素移除。

所以我们需要移除窗口头部的元素，也需要在窗口尾部增加或删除元素，自然就想到用双端队列来模拟滑动窗口。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;Deque<Integer> que = new ArrayDeque<>();int[] ans = new int[n - k + 1];for(int i = 0; i < n; i++){// 1、入队前需要删除比它小的所有元素while(!que.isEmpty() && nums[que.getLast()] <= nums[i]){que.removeLast();}que.addLast(i);// 2、如果窗口长度大于k，删除队首元素if(que.getFirst() <= i - k){que.removeFirst();}// 3、记录答案if(i >= k - 1){ans[i - k + 1] = nums[que.getFirst()];}}return ans;}
}