滑动窗口最大值问题

前言:滑动窗口最大值问题是很经典的算法问题。本文描述了它的求解过程,分析了时间复杂度,证明了其正确性。

什么是滑动窗口最大值问题

用一个长度固定的滑动窗口W在一个数组上逐元素滑动,求每次滑动后W内的最大元素。例如:长度为3的滑动窗口在数组[3,4,1,5,2]上滑动,在(a)和(b)两个时刻窗口内最大值分别为4和5。如下图所示:

《滑动窗口最大值问题》

你可以在leetcode上找到相关题目。

最容易想到的方法就是遍历每一时刻下滑动窗口内的所有元素,找到其最大值。整个过程简单直观,无需证明。复杂度上,易得空间复杂度是O(1),时间复杂度是O(N*K),其中N是数组长度,K是滑动窗口大小。因为需要滑动N次,每次遍历K个元素。

高阶解法

高阶解法在整个滑动过程中维护了一个队列Q。某时刻滑窗滑入的新元素记为x、滑出的旧元素记为z,则Q的更新步骤为:

  • 更新步骤一: 从Q的尾部依次弹出所有小于x的元素,然后把x压入Q的队尾
  • 更新步骤二: 如果Q的队首元素等于z,则Q弹出队首

执行以上操作后,Q的队首元素即为当前滑动窗口最大值。过程如图所示:

《滑动窗口最大值问题》

复杂度分析

空间上,需要额外的空间存储Q,Q的最大长度不超过K,因此空间复杂度是O(K)。

时间上,共迭代了N次,每次需要对Q做压入和弹出操作。最差的情况,某次迭代会弹出Q所有元素。Q的长度最大为K,所以貌似时间代价是O(NK);但实际上,从整体看,所有的元素都会压入一次,弹出一次,所以实际复杂度其实为O(N)。

证明

算法每次迭代都维持了一个条件不变式:

  • 条件一:Q是W的子序列。

  • 条件二:在W中,\(q_0\)是最大的元素,\(q_{i+1}\)\(q_{i}\)之后最大的元素。数组下标从0开始。

《滑动窗口最大值问题》

例如上图中,

  • Q=(8,6,4)是W的子序列
  • 在W中,8是W中最大的元素,6是8之后最大的元素,4是6之后最大的元素

值得注意的是,如果最大的元素存在多个,则认为是它们中的第一个。

过程分析

按照上文的更新规则,更新过程可以表述为:

  1. 滑窗纳入新元素x,x挤掉Q尾部所有小于它的元素,然后追加到Q。
  2. 滑窗弹出旧元素z,如果Q首元素等于z,则从Q弹出首元素

我们先来关注过程一。过程一可能有几个情况:

Case 1: x挤掉了Q的所有元素,说明它大于Q中所有元素,此时Q中只剩下x,显然这时候满足条件二。

《滑动窗口最大值问题》

Case 2: x没有挤掉任何Q的元素,说明x小于等于Q的所有元素。此时x会追加到Q的尾部,显然这时候满足条件二。

《滑动窗口最大值问题》

Case 3:x挤掉了Q的一部分元素,说明x大于Q尾部的一个或多个元素。

《滑动窗口最大值问题》

我们假设

\[q_k \ge x > \{ q_{k+1},…,q_m \} \]

则x会挤掉原来的 \(\{ q_{k+1},…,q_m \}\) 成为新的\(q_{k+1}\)

此时条件二成立:x比\(q_0\)小,不会动摇它的地位;x比\(q_{k+1}\)大,而后者是W中\(q_k\)之后最大的元素,因此x自然也是\(q_k\)之后最大的元素,那么x成为新的\(q_{k+1}\)后,自然满足条件二。

此时我们关注过程一。如果滑窗弹出的元素就是\(q_0\),那么Q自然也应该弹出\(q_0\),这样才能满足条件一。

  • 如果W弹出的元素z不等于\(q_0\),那么无需处理,如下图中情况(a)所示。

  • 如果z等于\(q_0\),那么可以确定弹出的就是\(q_0\),毕竟\(q_0\)是W中的最大元素(如果最大元素有多个则为第一个)。此时W和Q都弹出\(q_0\)后,依然符合条件一和条件二,这里不再证明。情况如下图(b)所示。

《滑动窗口最大值问题》

至此,证明完毕。

我们可以简单理解一下:Q是W的子序列,当W失去元素z时,Q自然也要失去它;如果W新来了一个很大的元素x,那么直到它被弹出之前,在前面比它小的元素是没有出头之日的。在它弹出之后,它前面的元素自然也早被弹出了。所以在前面比它小的元素都没有用,可以即刻弹出。

    原文作者:呆呆熊大人
    原文地址: https://www.cnblogs.com/mrrobot/p/16488463.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞