Karlblogs

Here remains my dream.

程序设计#4%2 - 【经典算法】双指针和滑动窗口·第三部分

16 min

在上一期的【双指针和滑动窗口·第二部分】，我们着重接触了滑动窗口的两种最基本情况：定长窗口（常用于寻找子数组求和的最大值，子串内最多元音数等问题）以及不定长窗口（例如上一期 leco 76 为代表的“越短越好”窗口和 leco 1658 为代表的“越长越好”窗口）。

但是更多时候我们不能单纯地使用这一类窗口。比如，如果我们需要求得每次窗口移动时，窗口内的最大值，这时候以过去的技巧来说会很麻烦，最直观的想法就是对每个窗口进行排序。但是那样的时间复杂度会退化到 O(nk)，数组长度大起来这就不可接受了。所以我们得给上一期探照灯，也就是朴素的滑动窗口，加一些 plugin。

求窗口内的最大/小值 - 单调队列

对于求最值，最朴素的观点当然就是通过遍历每一个窗口，接着寻找最值。简单遍历的时间复杂度是 O(k)，加上滑动窗口本身的复杂度 O(n)，总的时间复杂度就会退化到 O(nk)，这是不可接受的。因此我们借助一些新的工具，这个工具能够时刻返回窗口内最大/最小的元素。

这个工具叫做单调队列（monotonic queue），一个单调队列中的所有元素总保持单调性。它和通常的队列一样，有一个头和一个尾，我们压入元素时都是从队尾压入。

能从两端进，两端出的数据结构叫做双端队列（double-ended queue，简称 deque）。

首先应该做的是为这个双端队列定下三条规则。

  1. （入队）当一个新元素入队时，它应该从队尾开始，把所有比自己小的元素全部从队尾移出队列，然后自己进入。这条规则保证了队列中所有的元素必定是单调递减的。
  2. （取队头）队列是单调递减的，因此队头永远是最大值。
  3. （过期）每压入一个元素，都应该判断当前队头元素是否已经不在窗口内。如果是就把队头元素移出队列。

*取最小值只需要改为入队时移出所有比自己大的元素。*现在是第二个问题：应该存储下标，还是元素本身？

答案是下标。我们需要根据队列内元素在原数组中的下标来决定是否移除队头元素（第三条规则），假如 nums = [2, 2, 2], k = 3，我们无法区分这三个 2。

现在我们通过一个实际的例子来看看单调队列是如何工作的。

nums = [1, 3, -1, -5, 3, 6, 7], k = 3
此处用到的单调递减队列称作 q
deque1
deque1
deque2
deque2

理论存在，实践开始。Go 中没有内置的双端队列1，我们使用一个切片来模拟。

type Deque []int

func (d *Deque) PushBack(element int) { *d = append(*d, element) }
func (d *Deque) PopBack()             { *d = (*d)[:len(*d)-1] }
func (d *Deque) Front() int           { return (*d)[0] }
func (d *Deque) Back() int            { return (*d)[len(*d)-1] }
func (d *Deque) IsEmpty() bool        { return len(*d) == 0 }
func (d *Deque) PopFront(l int) {
	if !d.IsEmpty() && d.Front() < l { // 这是一个判断元素的逻辑，只有队头元素过期才会移出，否则什么都不做
		*d = (*d)[1:]
	}
}

有了单调队列，我们只需要套用滑动窗口的公式就能解决模板题了。

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	line, _ := reader.ReadString('\n')
	parts := strings.Fields(line)
	n, _ := strconv.Atoi(parts[0])
	k, _ := strconv.Atoi(parts[1])

	line, _ = reader.ReadString('\n')
	parts = strings.Fields(line)
	nums := make([]int, n)
	for i := range n {
		nums[i], _ = strconv.Atoi(parts[i])
	}

	var mind, maxd Deque
	minRes := make([]string, 0, n-k+1)
	maxRes := make([]string, 0, n-k+1)

	for i, num := range nums {
		for !mind.IsEmpty() && num <= nums[mind.Back()] { // 存储的是下标，因此要用 nums[i] 访问实际值
			mind.PopBack()
		}
		mind.PushBack(i)
		mind.PopFront(i - k + 1) // 当前窗口的左端

		for !maxd.IsEmpty() && num >= nums[maxd.Back()] {
			maxd.PopBack()
		}
		maxd.PushBack(i)
		maxd.PopFront(i - k + 1)

		if i >= k-1 {
			minRes = append(minRes, strconv.Itoa(nums[mind.Front()]))
			maxRes = append(maxRes, strconv.Itoa(nums[maxd.Front()]))
		}
	}

	fmt.Fprintln(writer, strings.Join(minRes, " "))
	fmt.Fprintln(writer, strings.Join(maxRes, " "))
}

或者是 239. 滑动窗口最大值 - 力扣（LeetCode），其中 Deque 的定义不变。

func maxSlidingWindow(nums []int, k int) []int {
	n := len(nums)
    var maxd Deque
	maxRes := make([]int, 0, n-k+1)

	for i, num := range nums {
		for !maxd.IsEmpty() && num >= nums[maxd.Back()] { // 存储的是下标，因此要用 nums[i] 访问实际值
			maxd.PopBack()
		}
		maxd.PushBack(i)
		maxd.PopFront(i - k + 1) // 当前窗口的左端

		if i >= k-1 {
			maxRes = append(maxRes, nums[maxd.Front()])
		}
	}

	return maxRes
}

满足 K 个条件 - 求子数组个数

这里的满足 K 个条件通常指子数组中有 K 个字符或整数，或者是对子数组中的 K 个整数求积小于给定值。

先看两种简单的：越短越好和越长越好。

越长越好的子数组

首先看这一题：1358. 包含所有三种字符的子字符串数目 - 力扣（LeetCode）。

先想象一下，我们从前三个字符开始，扫描子字符串，然后计算字符数，这样的暴力解法会造成非常恐怖的时间消耗。

所以我们试着总结一下子字符串的特点，看看能不能避免掉暴力搜索。

s = "aacbbabcc"

我们发现 s 中，从第一个字符开始搜索，第一个满足要求的子字符串是 s[0:4] == "aacb" 。

那我们就发现，s[0:4], s[0:5], ..., s[0:9]，这几个子串也是满足要求的，因为他们一定包含了前四个字符 "aacb"。这些加起来一共是 len(s)-r，其中 r 是当前窗口的右端点，此时答案加上 6（9-3）。

然后是 s[1:4] == "acb"，这同样满足条件，所以 s[1:4], s[1:5], ..., s[1:9] 这些也都是满足条件的，一共是 len(s)-r，也就是 6 个。

以此类推，也就得到了越长越好子数组的解法。

func numberOfSubstrings(s string) int {
    var freq [3]int
    var l, ans int
    for r, ch := range s {
        freq[ch-'a']++ // 0、1 和 2 分别代表 a、b 和 c
        for freq[0] > 0 && freq[1] > 0 && freq[2] > 0 { // 子串中同时包含 a、b 和 c
            ans += len(s)-r
            freq[s[l]-'a']--
            l++
        }
    }
    return ans
}

因此我们能从 leco1358 中抽象出一个具有普遍性的解法：一旦窗口扫描到一个符合条件的窗口，那么此时记 r 为窗口的右端点，一共有 len(arr)-r 个窗口符合条件，接着继续往后扫描即可。

因此 2962. 统计最大元素出现至少 K 次的子数组 - 力扣（LeetCode） 除了把字符串换成了数组，其余的思想是完全一致的。为了节约时间，可使用 slices 包的 slices.Max() 函数快速获得数组内的最大值。

func countSubarrays(nums []int, k int) int64 {
    target := slices.Max(nums)
    var l, now int
    var ans int64
    for r, num := range nums {
        if num == target {
            now++
        }
        for now >= k {
            ans += int64(len(nums)-r) // 当前窗口符合条件，意味着有 len(nums)-r 个窗口符合条件。
            if nums[l] == target { // 窗口收缩
                now--
            }
            l++
        }
    }
    return ans
}

当然，除了越长越好，还有一种越短越好的子数组，这时候我们换一个思路。

越短越好的子数组

这类问题最经典的就是寻找子数组求和不大于给定值。

不过这里有个求积的，也就是713. 乘积小于 K 的子数组 - 力扣（LeetCode）。

因为是正整数求积，所以当 k <= 1 时，不可能有子数组符合条件。

接着我们为了避免暴力搜索，观察一下满足条件的子数组有什么特征。

nums = [2,3,5,6,7,1,1,2]
k    = 100

第一个满足条件的子数组是 [2]，没什么特别的。

第二个满足条件的子数组是 [2, 3]，这时候我们发现，以 3 为右端点的子数组中，一共有 2 个子数组符合条件，分别是 [2, 3] 和 [3]。

第三个满足条件的子数组是 [2, 3, 5]，与第二个类似，以 5 为右端点的子数组中，一共有 3 个子数组符合条件，分别是 [2, 3, 5]、[3, 5] 和 [5]。

原因是，右端点相同，子数组越短当然子数组求积越小，就越能符合条件。

记当前窗口右端点为 r，左端点为 l，显然此时右端点相同的子数组一共有 r-l+1 个。

将上面的逻辑融入滑动窗口的模板中，于是得到了这里的代码。

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k <= 1 { // 子数组求积不可能比这还要小，跳过
        return 0
    }
    
    var l, ans int
    var now int = 1
    for r, num := range nums {
        now *= num
        for now >= k { // 收缩的条件
            now /= nums[l]
            l++
        }
        ans += r-l+1 // 相同右端点一共有 r-l+1 个子数组
    }
    return ans
}

有一道困难题的思路与这非常类似：2302. 统计得分小于 K 的子数组数目 - 力扣（LeetCode）。

上面的结论可以直接套用：右端点相同，子数组越短那么子数组的得分必定越小。

于是能直接推出代码，如下。

func countSubarrays(nums []int, k int64) (ans int64) {
    var now, l int
    
    for r := range nums {
        now += nums[r]
        for int64(now * (r-l+1)) >= k { // 得分超过了 k
            now -= nums[l]
            l++
        }
        ans += int64(r-l+1) // 右端点为 r，符合条件的子数组数目
    }
    return ans
}

恰好满足 K 个条件

我们常见的恰好满足 K 个条件，大多是在数组中寻找一个求和为 K 的子数组。

如果要用通常的滑动窗口思路解决，那么直接写判断子数组和的逻辑会非常复杂，因为一旦移动端点，子数组的和就可能会变。也就是说：

  • 如果我移动 r，我可能会找到一个以 l 开头的更长的合格子数组。
  • 如果我移动 l，我可能会找到一个以 r 结尾的更短的合格子数组。

对于这种情况，我们直接给出公式：ans = AtMost(K)-AtMost(K-1)，AtMost(K) 这个函数能够求出和小于或等于 K 的子数组数目。证明在下方。

看一道例题：930. 和相同的二元子数组 - 力扣（LeetCode）

这就是一道标准的恰好满足 K 个条件的滑动窗口题。

要找恰好求和等于 goal 的数组，如果我们直接求解，这就相当于暴力了：需要枚举每一个左端点和右端点。

我们看看上面的越短越好的子数组，假如我们需要求的是求和小于或等于 goal 的子数组，我们在上面已经知道怎么做了。

这时候，我们得到的子数组数目一共包含了 goal, goal-1, goal-2, ..., 0 的组合。注意看！里面是包含了等于 goal 的子数组数目的。

那么下一步就很清晰了，我们只要求出包含了 goal-1, goal-2, ..., 0 的组合，然后用前面求出的减去这个，答案就出来了。

这等价于求和小于或等于 goal-1 的子数组。

我们套用上面公式的 AtMost() 函数，给出答案。

func AtMost(K int, nums []int) int {
    var l, now int
    var ans int
    for r := range nums {
        now += nums[r]
        for now > K && l <= r {
            // 注意，当 K == -1（即 goal == 0） 时，这个条件是恒满足的，因此需要判断是否越界
            now -= nums[l]
            l++
        }
        ans += r-l+1
    }
    return ans
}

func numSubarraysWithSum(nums []int, goal int) int {
    return AtMost(goal, nums)-AtMost(goal-1, nums)
}

那么，从定长滑动窗口开始，到这里的更加灵活的滑动窗口，我们一共经历了三个部分，分别是：

  1. 快慢指针和对撞指针
    • 数组去重
    • 寻找链表中点与链表环的起点
    • 二分查找
    • 寻找元组问题（有序数组内的两数之和等）
  2. 滑动窗口 - 定长与不定长
    • 子数组和最大/小
    • 维护数组内元素的唯一性（基于哈希表）
    • 破洞数组
    • 循环数组内的滑动窗口（基于取余运算实现循环）
    • 反向窗口（正难则反思想）
    • 最小覆盖子串（越短越好的子数组）
  3. （本节）窗口内求最值和（最多/最少/恰好）满足 K 个条件
    • 单调队列
    • 求满足 K 个条件的子数组的个数

下一期将会基于一道困难题： LeetCode 42. 接雨水 继续双指针算法的学习，并且我们将会引入多数组中的指针协作（也就是两个指针在两个不同的数组里运动）。

🎉撒花🎉

Footnotes

  1. C++ 标准模板库有一个 deque 模板，跟这里使用的是一致的，可通过 #include <deque> 引入。 ↩

Golang 程序设计