了解面试必会算法Sliding Window 模式的前世今生

大家好，今天我们来聊一聊sliding window pattern。又是给有个机会给班花讲题的好机会，不能错过！

Sliding Window Pattern，中文名字叫滑动窗口模式，是一种常见的算法思想。它可以用来解决很多问题，比如：

Sliding Window Pattern 的优缺点

它具有以下优点：

• 可以有效地解决很多问题：Sliding Window Pattern 可以用于解决很多问题，比如求最大值、最小值、平均值、子串、子序列的长度、最长公共子序列、最长上升子序列等。
• 时间复杂度较低：Sliding Window Pattern 的一般时间复杂度为 O(n)，对于一些特殊问题，时间复杂度甚至可以达到 O(1)。
• 代码实现简单：Sliding Window Pattern 的代码实现非常简单，只需要维护一个窗口，然后在窗口滑动过程中不断地更新窗口内的值即可。

Sliding Window 算法也存在一些缺点：

• 需要额外空间：Sliding Window Pattern 需要额外存储窗口内的元素，因此会增加空间复杂度。
• 适用范围有限：Sliding Window Pattern 并不是所有问题都适用，只有满足特定条件的问题才能使用 Sliding Window Pattern。

怎么样？是不是依然觉得有些不理解，那么上图说话

L和R指针分别都指向a, R走到b，这时候将a放入HashSet，接下来放入b；因为窗口大小为3，那么R继续向??走，走到c，最终将c放入HashSet。

当然了如何白月光还是觉得这个算法不好记，我们就那个例子让她印象更加深刻吧

我们可以把数组看成一条河流，窗口就像一条船。船从左到右航行，每次经过一个元素，就把这个元素记录下来。当船航行到河流的尽头时，我们就得到了河流中最大值的滑动窗口。

伪代码实现

function sliding_window(array, window_size)
  # 初始化窗口
  window = []
  for i in range(window_size):
    window.append(array[i])

  # 滑动窗口
  for i in range(window_size, len(array)):
    # 更新窗口
    window.pop(0)
    window.append(array[i])

    # 计算窗口内的值
    ...

  # 返回窗口内的值
  return window

具体用Java语言实现的例子可以参考小白理解Leetcode系列

小白水平理解面试经典题目LeetCode 594 最大和谐字符串