洛谷P1886 滑动窗口 /【模板】单调队列

博主： Faulkner
发布时间：2023 年 11 月 26 日
665 次浏览
3 条评论
2307字数
分类：默认分类

# 滑动窗口 /【模板】单调队列

## 题目描述

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is $[1,3,-1,-3,5,3,6,7]$, and $k = 3$。

| 窗口位置            | 最小值 | 最大值 |
| ------------------- | ------ | ------ |
| [1 3 -1] -3 5 3 6 7 | -1     | 3      |
| 1 [3 -1 -3] 5 3 6 7 | -3     | 3      |
| 1 3 [-1 -3 5] 3 6 7 | -3     | 5      |
| 1 3 -1 [-3 5 3] 6 7 | -3     | 5      |
| 1 3 -1 -3 [5 3 6] 7 | 3      | 6      |
| 1 3 -1 -3 5 [3 6 7] | 3      | 7      |

## 输入格式

输入一共有两行，第一行有两个正整数 $n,k$。
第二行 $n$ 个整数，表示序列 $a$

## 输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

## 样例 #1

### 样例输入 #1

```
8 3
1 3 -1 -3 5 3 6 7
```

### 样例输出 #1

```
-1 -3 -3 -3 3 3
3 3 5 5 6 7
```

## 提示

【数据范围】
对于 $50\%$ 的数据，$1 \le n \le 10^5$；
对于 $100\%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in [-2^{31},2^{31})$。、

## 分析

这题是一道经典的单调队列板子题，单调队列是一种特殊的队列，它具有队列中的元素按照从大到小（或从小到大）的顺序排列的特点。单调队列题型可以出的题目很少，算是一种冷门考点了。这种滑动窗口类的题目事实上可能是这种数据结构最多的考点。

如果读者之前没有学过单调队列，这道题目读者可能并不能把单调队列的定义和这题目联系起来，因为看起来确实没有什么关联。

现在我们如果分析这道题的朴素题解，一个自然的想法便是全部遍历一次，暴力出结果。可惜这样的复杂度很高，算法效率太低，而单调队列解法某种意义上是在这种朴素算法基础上的一种优化。我们现在假设一个数组 `q`用于模拟滑动窗口，设在滑动窗口中有两个数 `w[i]`和 `w[j]`且 `i < j`。下面是对于大体思路的分析：

- 我现在要求滑动窗口最大值，不妨设 `w[i] < w[j]`，在这种情况下当滑动窗口向右移动时，只要 `w[i]`还在窗口中，那么 `w[j]`一定也还在窗口中。这就产生了一个事实：`w[i]`永远不可能被用到，因为就算是 `w[i]`出窗口了，`w[j]`依然在窗口内，而 `w[i] < w[j]`要找的最大值一定是 `w[j]`。用一个例子来说明就是新来了一个选手比你小却比你厉害，而且你们的技术以相同的速率正增长，这样你是没有翻身之日的，因为到最后你退役了你的水平都没他高，更何况他那个时候还没退役。因此，由于 `w[j]` 的存在，`w[i]` 一定不会是窗口中的最值，他是一个“废数”，这个时候可以将 `w[i]`永久移除。
- 类比上述过程，滑动窗口向右移动时，要进入数组 `w`的新元素要和尾元素进行对比：如果新元素大于等于数组尾元素，那么数组尾的元素就需要被移除。我们需要不断地进行此项操作，直到新元素遇见边界或者比他大的元素。同时我们**有的时候**还需要移除数组首元素将第二个元素制造为新首元素保证数组中的所有元素都在窗口中，因此当数组首元素在窗口左边的时候，移除首元素。这样可以轻松分析得到数组 `w`是一个**递减**的数组，要求的**窗口内最大值**便是 `w`**首元素**。很好，以上数组 `w`就是模拟的单调队列。
- 如果我要求滑动窗口最小值，分析过程类似上面，不多赘述。

以上就是对于实现功能的思路的分析，并不难，接下来便是对实现的探讨。

- 如果队列不为空，并且队列头部的元素索引已经不在窗口内（即小于当前元素索引减去窗口大小加一），则队列头部元素出队。
- 在保证队列中的元素从头到尾是递增的前提下，将当前元素索引加入队列。如果新元素比队尾元素小，则队尾元素出队，然后循环此操作，直到新元素遇见边界或者比他小的元素，这样保证了队列头部的元素是当前窗口的最小值且整个递增。
- 一旦窗口的大小达到 `k`，输出队列头元素，即为当前窗口的最小值。
- 最大值与上述过程相反。

## 代码

下面给出代码：

```c++
#include <cstdio>

const int N = 1000010;
int a[N], q[N], tt = -1, hh;

int main()
{
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", a + i);
    if (hh <= tt && q[hh] < i - k + 1)
      hh++;
    while (hh <= tt && a[i] <= a[q[tt]])
      tt--;
    q[++tt] = i;
    if (i >= k - 1)
      printf("%d ", a[q[hh]]);
  }
  printf("\n");
  tt = -1;
  hh = 0;
  for (int i = 0; i < n; i++)
  {
    if (hh <= tt && q[hh] < i - k + 1)
      hh++;
    while (hh <= tt && a[i] >= a[q[tt]])
      tt--;
    q[++tt] = i;
    if (i >= k - 1)
      printf("%d ", a[q[hh]]);
  }
  return 0;
}
```

最后修改：2024 年 10 月 23 日

如果觉得我的文章对你有用，请随意赞赏

3 条评论

vqfttgfsfj
November 20th, 2024 at 07:45 am

真好呢

回复
ekogggzmey
November 20th, 2024 at 07:43 am

真棒！

回复
潜心学习的男士
November 29th, 2023 at 05:14 pm

好！

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

洛谷P1886 滑动窗口 /【模板】单调队列

Faulkner • 2023 年 11 月 26 日

# 滑动窗口 /【模板】单调队列

## 题目描述

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is $[1,3,-1,-3,5,3,6,7]$, and $k = 3$。

## 输入格式

输入一共有两行，第一行有两个正整数 $n,k$。
第二行 $n$ 个整数，表示序列 $a$

## 输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

## 样例 #1

### 样例输入 #1

```
8 3
1 3 -1 -3 5 3 6 7
```

### 样例输出 #1

```
-1 -3 -3 -3 3 3
3 3 5 5 6 7
```

## 提示

【数据范围】
对于 $50\%$ 的数据，$1 \le n \le 10^5$；
对于 $100\%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in [-2^{31},2^{31})$。、

## 分析

如果读者之前没有学过单调队列，这道题目读者可能并不能把单调队列的定义和这题目联系起来，因为看起来确实没有什么关联。

以上就是对于实现功能的思路的分析，并不难，接下来便是对实现的探讨。

## 代码

下面给出代码：

```c++
#include <cstdio>

const int N = 1000010;
int a[N], q[N], tt = -1, hh;

3 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

洛谷P1886 滑动窗口 /【模板】单调队列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款