滑动窗口最大值（239）

有读者小伙伴建议讲一下滑动窗口相关题型，因为经常面试会被问到。所以就开了这个系列（所以如果大家有想让分享的题型都可以留言区告诉我，任何事情我觉得都需要有反馈。比如一个错误，你不反馈，我不知道..那就只能这样过去了..）闲话不啰嗦，直接看题！

01、题目分析

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

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


返回滑动窗口中的最大值所构成的数组。


示例:

  1. 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
  2. 输出: [3,3,5,5,6,7] 
  3. 解释: 
  5.   滑动窗口的位置                最大值
  6. ---------------               -----
  7. [1  3  -1] -3  5  3  6  7       3
  8.  1 [3  -1  -3] 5  3  6  7       3
  9.  1  3 [-1  -3  5] 3  6  7       5
  10.  1  3  -1 [-3  5  3] 6  7       5
  11.  1  3  -1  -3 [5  3  6] 7       6
  12.  1  3  -1  -3  5 [3  6  7]      7

本题有一定难度！建议认真阅读

并课后练习~

02、题目分析

本题对于题目没有太多需要额外说明的，应该都能理解，直接进行分析。我们很容易想到，可以通过遍历所有的滑动窗口，找到每一个窗口的最大值，来进行暴力求解。那一共有多少个滑动窗口呢，小学题目，可以得到共有 L-k+1 个窗口。


假设 nums = [1,3,-1,-3,5,3,6,7]，和 k = 3，窗口数为6

img

根据分析，直接完成代码：

  1. class Solution {
  2.     public int[] maxSlidingWindow(int[] nums, int k) {
  3.         int len = nums.length;
  4.         if (len * k == 0) return new int[0];
  5.         int [] win = new int[len - k + 1];
  6.         //遍历所有的滑动窗口
  7.         for (int i = 0; i < len - k + 1; i++) {
  8.             int max = Integer.MIN_VALUE;
  9.             //找到每一个滑动窗口的最大值
  10.             for(int j = i; j < i + k; j++) {
  11.                 max = Math.max(max, nums[j]);
  12.             }
  13.             win[i] = max;
  14.         }
  15.         return win;
  16.     }
  17. }

运行结果：

img


It’s Bullshit！结果令我们很不满意，时间复杂度达到了O(LK)，如果面试问到这道题，基本上只写出这样的代码，一定就挂掉了。那我们怎么样优化时间复杂度呢？有没有可以O(L)的实现呢？=_=

03、线性题解

这里不卖关子，其实这道题比较经典，我们可以采用队列，DP，堆等方式进行求解，所有思路的主要源头应该都是在窗口滑动的过程中，如何更快的完成查找最大值的过程。但是最典型的解法还是使用双端队列。具体怎么来求解，一起看一下。


首先，我们了解一下，什么是双端队列：是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出或者插入。

img

我们可以利用双端队列来实现一个窗口，目的是让该窗口可以做到张弛有度（汉语博大精深，也就是长度动态变化。其实用游标或者其他解法的目的都是一样的，就是去维护一个可变长的窗口）


然后我们再做一件事，只要遍历该数组，同时在双端队列的头去维护当前窗口的最大值（在遍历过程中，发现当前元素比队列中的元素大，就将原来队列中的元素祭天），在整个遍历的过程中我们再记录下每一个窗口的最大值到结果数组中。最终结果数组就是我们想要的，整体图解如下。


假设 nums = [1,3,-1,-3,5,3,6,7]，和 k = 3

img

（小浩os：我觉得自己画的这个图对于双端队列的解法还是介绍的比较清晰的，大家好好看一下哦，这样我的努力也就没有白费呢。）


根据分析，得出代码：

  1. func maxSlidingWindow(nums []int, k int) []int {
  2.     if len(nums) == 0 {
  3.         return []int{}
  4.     }
  5.     //用切片模拟一个双端队列
  6.     queue := []int{}
  7.     result := []int{}
  8.     for i := range nums {
  9.         for i > 0 && (len(queue) > 0) && nums[i] > queue[len(queue)-1] {
  10.             //将比当前元素小的元素祭天
  11.             queue = queue[:len(queue)-1]
  12.         }
  13.         //将当前元素放入queue中
  14.         queue = append(queue, nums[i])
  15.         if i >= k && nums[i-k] == queue[0] {
  16.             //维护队列，保证其头元素为当前窗口最大值
  17.             queue = queue[1:]
  18.         }
  19.         if i >= k-1 {
  20.             //放入结果数组
  21.             result = append(result, queue[0])
  22.         }
  23.     }
  24.     return result
  25. }

执行结果：

img


Perfact~题目完成！看着一下子超越百分之99的用户，是不是感觉很爽呢~