滑动窗口中的最小值

在日常的算法面试和刷题过程中，滑动窗口问题是非常常见的类型。今天我们来详细解答如何通过单调队列的方法找到滑动窗口中的最小值，并通过具体代码示例和步骤拆解，帮助大家更好地理解这一算法。

问题描述

给定一个数组和一个整数 k，我们需要找到该数组中每个大小为 k 的连续子数组中的最小值。

举例来说，给定数组 a = [2, 1, 3, 4, 5]，窗口大小为 k=3，我们需要找到以下滑动窗口中的最小值：

• [2, 1, 3] 的最小值为 1
• [1, 3, 4] 的最小值为 1
• [3, 4, 5] 的最小值为 3

输出结果应该是：1 1 3

思路

我们使用单调队列来解决这一问题。队列中存储的是数组中元素的下标，队列中的元素保持单调递减。这样队头元素总是滑动窗口的最小值。

主要步骤：

1. 保持队列单调性：当有新的元素进入窗口时，我们需要移除队列中比新元素大的值，因为这些值在窗口中已经不可能成为最小值。
2. 移除过期元素：当滑动窗口右移时，窗口中最左边的元素可能已经超出了窗口范围，我们需要从队列中移除它。
3. 输出当前窗口的最小值：当窗口大小达到 k 时，输出队头元素即为当前窗口的最小值。

代码实现

int hh = 0, tt = -1;  // 初始化队列的头和尾指针
for (int i = 1; i <= n; i++) {
    // 判断队头是否在窗口范围内，不在则移除
    if (hh <= tt && q[hh] < i - k + 1) hh++;
    
    // 保持队列单调递减，移除比当前元素大的队尾元素
    while (hh <= tt && a[i] <= a[q[tt]]) tt--;
    
    // 当前元素入队
    q[++tt] = i;
    
    // 窗口达到大小 k 时，输出当前窗口的最小值
    if (i > k - 1) cout << a[q[hh]] << " ";
}
puts("");  // 输出完毕后换行

详细示例分析

我们以 a = [2, 1, 3, 4, 5]，k=3 为例，通过每一步的分析，帮助大家更好地理解代码的执行过程。

第 1 步 (i=1)：

• 当前元素：a[1] = 2
• 判断是否移除队头元素：队列为空，不执行移除操作。
• 判断是否保持单调性：队列为空，不执行移除操作。
• 将 a[1] 的下标 1 入队，队列状态：q = [1]。
• 当前窗口还不足 k 个元素，不输出最小值。

第 2 步 (i=2)：

• 当前元素：a[2] = 1
• 判断是否移除队头元素：队列头元素 q[hh] = 1 还在窗口范围内，不移除。
• 保持单调性：当前元素 a[2] = 1 小于队尾元素 a[1] = 2，移除队尾元素。
• 将 a[2] 的下标 2 入队，队列状态：q = [2]。
• 当前窗口还不足 k 个元素，不输出最小值。

第 3 步 (i=3)：

• 当前元素：a[3] = 3
• 判断是否移除队头元素：队列头元素 q[hh] = 2 还在窗口范围内，不移除。
• 保持单调性：当前元素 a[3] = 3 大于队尾元素 a[2] = 1，不移除队尾元素。
• 将 a[3] 的下标 3 入队，队列状态：q = [2, 3]。
• 当前窗口已达到 k 个元素，输出当前窗口的最小值 a[q[hh]] = a[2] = 1。
• 输出：1

第 4 步 (i=4)：

• 当前元素：a[4] = 4
• 判断是否移除队头元素：队列头元素 q[hh] = 2 超出窗口范围，移除队头元素。
• 保持单调性：当前元素 a[4] = 4 大于队尾元素 a[3] = 3，不移除队尾元素。
• 将 a[4] 的下标 4 入队，队列状态：q = [3, 4]。
• 当前窗口已达到 k 个元素，输出当前窗口的最小值 a[q[hh]] = a[3] = 1。
• 输出：1

第 5 步 (i=5)：

• 当前元素：a[5] = 5
• 判断是否移除队头元素：队列头元素 q[hh] = 3 还在窗口范围内，不移除。
• 保持单调性：当前元素 a[5] = 5 大于队尾元素 a[4] = 4，不移除队尾元素。
• 将 a[5] 的下标 5 入队，队列状态：q = [3, 4, 5]。
• 当前窗口已达到 k 个元素，输出当前窗口的最小值 a[q[hh]] = a[3] = 3。
• 输出：3

最终输出：

1 1 3

关键部分解释

1. 移除队头元素：

   if (hh <= tt && q[hh] < i - k + 1) hh++;

   这个条件判断队列头元素是否超出了当前窗口范围，如果队头下标不在窗口内，就将其移除。

2. 保持单调队列：

   while (hh <= tt && a[i] <= a[q[tt]]) tt--;

   我们需要保证队列中的元素保持单调递减。每当有新元素加入队列时，我们移除所有比它大的元素，因为这些较大的元素在当前窗口中不可能再成为最小值。

3. 输出最小值：

   if (i > k - 1) cout << a[q[hh]] << " ";

   当遍历到第 k 个元素及以后时，窗口的大小达到 k，此时输出队列头的元素作为当前窗口的最小值。

总结

通过使用单调队列，我们能够高效地解决滑动窗口最小值问题。时间复杂度为 O(n)，因为每个元素最多入队和出队各一次。单调队列是一种非常有用的技巧，特别是在涉及动态范围查询的问题时。