从零学算法239

算法239"/>

从零学算法239

239.给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[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
示例 2：
输入：nums = [1], k = 1
输出：[1]

• 他人题解：提示的这么明显了，不用滑动窗口都说不过去了。我们先过一遍暴力解法，首先数组长度为 n 的话，窗口滑动过程是从 [i,j] 到 [i+1,j+1]，然后继续加 1 加 1。如果左端的 i 是固定的，也就是窗口滑动过程为 [i,j] 到 [i,j+1]，那么其实最大值 x 的获取就简单多了，要么是之前的最大值，要么就是新加进来的 nums[j+1]，所以 x(i,j+1) = max(x(i,j), nums[j+1]) 。问题就是现在 i 不固定，我们从 [i,j] 到 [i+1,j+1] 缺少的 nums[i] 可能就是之前的最大值，这也就导致我们每次都需要从新划分范围内重新遍历找出最大值。需要寻找 (n-k+1) 次，每次遍历 k 个数，时间复杂度几乎为 O(nk)，所以我们优化的点就在于怎样快速找到这个最大值。
• 好吧凭我自己是想不到，最终解法使用了双端队列，我们需要保证的有两点，第一点：队列中的数一定是属于窗口 [i,j] 中的数，第二点为了降低最大值的查询速度，也就是我们使用双端队列的原因，我们让队列中的值保持降序，这样每次存入我们最终的 ans 数组时，取首位元素存入即可。保证了这两点那就表示我们存入结果数组的数就和上面的例子1一样，每次存入的数在滑动窗口范围内，且是当前最大值。具体看代码。

•   public int[] maxSlidingWindow(int[] nums, int k) {// 无效情况先排除if(nums.length == 0 || k == 0)return new int[0];// 结果数组int[] ans = new int[nums.length - k + 1];// 杀手锏，双端队列Deque<Integer> deque = new LinkedList<>();// 窗口的设定也挺巧妙的，i,j 从 [1-k,0] 不断后移，// 第一次正经得到范围的时候就是 [0,k-1]// 在这之前我们就只是老老实实存进队列，处理队列for(int i=1-k,j=0; j<nums.length; i++,j++){// 队列首存的是最大值，如果窗口已经形成，并且在滑动过程中排除这个数了// 那队列当然也要移除这个数，也就是我们要保证的第一点if(i>0 && nums[i-1] == deque.getFirst())deque.removeFirst();// 为了保持降序，移除之前的元素，为什么不会对我们最终结果造成影响// 因为我们给 nums[j] 腾位置，因此去掉的数最后都是无用的，// 这里去掉无用的数，加上上面的去掉队列的数// 两相结合保证了我们的第一点// 而无用的原因就是，nums[j] 在我们当前合法范围内(即 [i,j])，// 并且他最大的话我们就只用得上它，用不上去掉的数，这也就是我们保证的第二点// 或者引用他人的一句话：当一个元素进入队列的时候，它前面所有比它小的元素就不会再对答案产生影响while(!deque.isEmpty() && deque.getLast() < nums[j])deque.removeLast();// 位置腾好了，放心加进队列即可，保管你是保持降序的deque.addLast(nums[j]);// i==0 说明第一次到了正经范围了 [0,k-1]，也就是窗口终于形成了// 因此可以开始计算结果了if(i>=0)ans[i] = deque.getFirst();}return ans;}
  

• 当然窗口形成也可以拆分成两部分，形成前后，这样虽然代码更长，但是逻辑更清晰且去掉了冗余的判断

•   public int[] maxAltitude(int[] heights, int limit) {if(heights.length == 0 || limit == 0) return new int[0];Deque<Integer> deque = new LinkedList<>();int[] res = new int[heights.length - limit + 1];// 未形成窗口for(int i = 0; i < limit; i++) {while(!deque.isEmpty() && deque.peekLast() < heights[i])deque.removeLast();deque.addLast(heights[i]);}// 别忘了窗口已经形成了，可以记录一次结果了res[0] = deque.peekFirst();// 形成窗口后，也就不需要判断之前的 i>0,i>=0 了for(int i = limit; i < heights.length; i++) {if(deque.peekFirst() == heights[i - limit])deque.removeFirst();while(!deque.isEmpty() && deque.peekLast() < heights[i])deque.removeLast();deque.addLast(heights[i]);res[i - limit + 1] = deque.peekFirst();}return res;}