前端算法--滑动窗口

滑动窗口概述

滑动窗口（Sliding Window）法，也叫尺取法，可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题，在一个特定大小的字符串或数组上进行操作，而不在整个字符串或数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。往往类似于“请找到满足xx的最x的区间（子串、子数组）的xx”这类问题都可以使用该方法进行解决。

• 滑动： 说明这个窗口是移动的，也就是移动是按照一定方向来的。
• 窗口： 窗口大小并不是固定的，可以不断扩容直到满足一定的条件；也可以不断缩小，直到找到一个满足条件的最小窗口；当然也可以是固定大小。

算法基本思想：

字符串也可以转换成数组，其实本质上滑动窗口都是在数组上进行操作，对数组的操作我们一般会采用循环类方法，而滑动窗口方法则为了提升效率会采用进阶的循环，即两个指针：左指针left，右指针right。

两个指针之间的内容：[left…right]则构成了窗口（window），随着指针的不断移动，窗口的位置和大小都会发生变动，但窗口里面的数据始终是连续的，通过对这些数据的处理，就可以得到需要的结果。

如下图所示，设定滑动窗口（window）大小为 3，当滑动窗口每次划过数组时，计算当前滑动窗口中元素的和，得到结果 res：

结合上面的思路，可以设计一下滑动窗口的通用框架，伪代码如下：

var list = [...]

var left = 0; // 左指针
var right = 0; // 右指针

var window = [] 或 {}

while(right < list.length) { // 右指针小于边界
    window.add(list[right]);// 向窗口添加元素
    right++;// 移动right扩大窗口
    // 如果符合要求，说明窗口构造完成，移动 left 缩小窗口 
    while (window 符合要求（length < 3）) {

        // ...针对窗口内容处理
        sum(window) // 求和res

        window.remove(list[left]); // 将元素移出窗口
        left++; // 缩小窗口
    }
}

框架由两个while循环构成，外层控制窗口扩展，内层控制窗口收缩，下面来举几个例子。

Leetcode算法原题：

3 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

首先，需要明确子串一般是连续的，子序列一般是不连续的，题目中求子串，很容易联想到滑动窗口解法。

根据题目可以知道，窗口的大小是不固定的，所以该题目难点在于我们需要找到一个临界条件来判断合适调整窗口里面的数据，即内层的while循环什么时候执行。

由于题目要求的是无重复字符，对于常见的算法中，很多情况情况下需要利用Map来统计一个字符串中字符是否重复，即key值为单个字符，value为该字符出现的次数，如下：

var str = 'abcdea'
var map = {}
for (var i = 0 ; i < str.length ; i++) {
    var cur = str[i]
    if (map[cur]) {
       map[cur] ++
    } else {
       map[cur] = 1
    }
}
map: {"a":2,"b":1,"c":1,"d":1,"e":1}

所以，当map里面的某个key对应的值大于1时，说明该字符串含有重复字符。利用这个思路，我们使用滑动窗口时，就可以作为window符合要求的条件判断，整体思路如下图（图片来自leetcode）：

其中，i，j两个指针分别对应left和right，通过不断变换窗口来计算每次变换后的连续子串长度。

解法：

var lengthOfLongestSubstring = function(s) {
    var map = {} // 用来计算每个字符出现的次数
    var left = 0,right = 0;
    var len = s.length
    var res = 0
    while(right < len) {
        var r = s[right]
        right++
        // 右指针的元素进入窗口
        if (map[r]) {
            map[r]++
        } else {
            map[r] = 1
        }

        // 发现窗口中有重复元素
        while(map[r] > 1) {
            var l = s[left]
            // 缩小窗口
            left++
            map[l]--
        }
        // 此时的窗口中必无重复值
        // 窗口每次变化 都记录长度 两两比较取最大值
        res = Math.max(res,right-left)
    }

    return res
};

时间复杂度： O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度： O(N)，其中 N 是字符串中不重复字符的个数，空间消耗于Map。

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]

示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]

示例 4：

输入：nums = [9,11], k = 2
输出：[11]

示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

在 LeetCode 上，这虽然是一道hard难度的题目，但是利用我们上面的滑动窗口框架思路，很容易就可以提供一种解法。

首先，题目中的窗口大小时固定的，所以我们只需要移动窗口，即同步移动left和right指针，而内层while循环的window符合要求条件就很简单了，直接判断窗口长度是否符合即可，核心代码如下：

var window = []
while (right < nums.length) {
    var r = nums[right]
    right++
    window.push(r)// 右边元素进入窗口
    while (window.length == k) { // 窗口长度符合k
       max(window) // 计算窗口中的最大值
        window.shift()// 左边元素移出窗口
        left++ // 窗口向右移动
    }
}

基本思路：

• 使用滑动窗口遍历数组。
• 窗口对象为一个数组，每次指针向右移动时，向数组中添加元素。
• 当窗口大小符合k时，计算窗口中的最大值，然后窗口整体向右移动。
• 当右指针到达边界时，遍历完成。

解法：

var maxSlidingWindow = function(nums, k) {
  if (k == 1) return nums
  var right = 0,left = 0
  var window = []
  var res = []

  while (right < nums.length) {
      var r = nums[right]
      right++
      window.push(r)
      while (window.length == k) {
          res.push(Math.max(...window)) // 利用Math.max求最大值
          window.shift()
          left++
      }
  }

  return res
};

但是作为一道hard难度的题目，其难度主要在于时间复杂度，上面解法中，我们每次对窗口中的数据求最大值，利用Math.max()方法，这其实是非常消耗性能的，底层其实会对窗口进行遍历，并取得到最大值，这样增加了很大一部分循环时间复杂度。

我们可以思考一下，窗口window只需要得到最大值，那么我们就可以将窗口设置为一个单调递减的数组队列，每当新进入窗口的元素比之前的还小时，就直接抛弃，这时的最大值还是上一次的最大值，这样就节省了时间，引入单调队列。

单调队列基本思路：

原始队列：[1 3 -1 -3 5 3]。

始终要维护队列保证其 递减 的特点，所以会有如下的事情发生：

操作	队列状态
1入队	[1]
3入队，比1大，1删除	[3]
-1入队	[3，-1]
-3入队	[3，-1，-3]
5入队，比-3大，删除前面元素，再依次比较删除	[5]
3入队	[5，3]

转换成代码如下：

 class maxQueue {
    constructor(){
        this.items = []
    }
    // 进入队列
    enqueue(ele){
      // 把前面比新元素小的元素都删掉
      while(this.items.length && this.items[this.items.length-1] < ele) {
        this.items.pop()
      }
      this.items.push(ele)
    }
    // 队首出队
    dequeue(ele){
      // 判断是否是需要移出的元素
      if (this.items.length && this.items[0] == ele) {
        this.items.shift()
      }
    }
    // 队首就是最大元素
    front(){
      return this.items[0]
    }
    max(){
        return this.front()// 队首就是最大元素
    }
}

引入优先队列之后，改造我们的整体解法，代码如下：

解法：

var maxSlidingWindow = function(nums, k) {
    if (k == 1) return nums
    var right = 0,left = 0
    var window = new maxQueue()
    var res = []

    while (right < nums.length) {
        var r = nums[right]
        right++
        window.enqueue(r)
        while (right-left >= k) {
            var l = nums[left]
            res.push(window.max())
            window.dequeue(l)
            left++
        }
    }
    return res
};

时间复杂度：O(N logN)，其中N是nums数组的长度。左指针和右指针分别会遍历整个字符串一次。在最坏情况下，数组nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(log N)，因此总时间复杂度为 O(N logN)

空间复杂度：O(N)，其中 N 是优先队列需要使用的空间。

76 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

这是一道hard难度的题目，主要难度在于两个字符串，同时需要在第一个字符串中寻找第二个字符串的排列组合，但归根到底还是寻找子串问题，可以对第一个字符串s进行滑动窗口算法。

首先，该题目的最终目的是要在s中找到含有t，但是这个含有不是和t相等，而是找到t的排列组合即是否含有t中的所有元素，由于t中可能包含有重复元素，在计算排列组合时，重复元素是不计入统计的，还是利用Map，先统计一下每个字符，代码如下：

var map = {}
var missingType = 0 // 记录不重复的字符个数

for (var c of t) {
    if (map[c]) {
        map[c]++
    } else {
        map[c] = 1
        missingType++
    }
}

得到map后，就可以利用map去s里面匹配，代码如下：

while(right < s.length) {
    var r = s[right]
    right++ 
    
    if (map.hasOwnProperty(r)) { // 每当进入窗口的字符在s中出现时，就将次数-1
        map[r]--
    }

    if (map[r] == 0) {// 当某个字符次数为0时，表示当前的这个字符就已经不缺
        missingType--
    }

    while(missingType == 0) { // 所有字符都匹配上，这时可以缩小窗口

        if (right - left < res.length) { // 取长度
            res = s.substring(left,right)
        }
        var l = s[left]
        left++
        map[l]++ // 每当字符移出窗口时，就将次数+1
        if (map[l] > 0) { // 如果当前的字符大于0，表示还缺少这个字符
            missingType++
        }
    }
}

我们在s 上滑动窗口，通过移动right指针不断扩张窗口。当窗口包含t全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口，missingType用来增加标志位记录重复字符。整体思路如下图（图片来自leetcode）：

最后，我们需要处理一些边界条件，例如s和t相等，或者s中完全不包含t的情况，完整解法如下：

解法：

var minWindow = function(s, t) {
    if (t.length > s.length) return ''
    if (t == s) return s
    var flag = false
    var map = {}
    var missingType = 0
    var res = s
    for (var c of t) {
        if (!map[c]) {
            map[c] = 1
            missingType++
        } else {
            map[c]++
        }
    }
    var left = 0,right = 0

    while(right < s.length) {
        var r = s[right]
        right++ 
        
        if (map.hasOwnProperty(r)) { // 每当进入窗口的字符在s中出现时，就将次数-1
            map[r]--
        }
    
        if (map[r] == 0) {// 当某个字符次数为0时，表示当前的这个字符就已经不缺
            missingType--
        }
    
        while(missingType == 0) { // 所有字符都匹配上，这时可以缩小窗口
            flag = true // 在s中找打过t
            if (right - left < res.length) { // 取长度
                res = s.substring(left,right)
            }
            var l = s[left]
            left++
            map[l]++ // 每当字符移出窗口时，就将次数+1
            if (map[l] > 0) { // 如果当前的字符大于0，表示还缺少这个字符
                missingType++
            }
        }
    }
    return !flag ? '' : res
}

时间复杂度： O(N)，其中 N 是字符串s的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度： O(N)，其中 N 是字符串中不重复字符的个数，空间消耗于Map。

总结

滑动窗口类问题是面试当中的 高频题，问题本身其实并不复杂，掌握好框架很重要。