题目描述

题目链接

给定一个大小为 $n \le 10^6$ 的数组。

有一个大小为 $k$ 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 $k$ 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，$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$ 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

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

输出样例：

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

算法1

(暴力枚举) O(nk)O(nk)

最直观最暴力的思想就是：

  • 维护一个滑动窗口
  • 每次向队尾添加新数字，将队头数字踢出
  • 每次遍历窗口，找到最大/最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cmath>

using namespace std;

const int N = 1000010;
int a[N], q[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    
    int i = 0, j = m - 1;
    for( i, j; j < n; j ++, i ++)
    {
        int minv = 1e9;
        for(int t = i; t <= j; t ++)
        {
            minv = min(minv, a[t]);
        }
        cout << minv << ' ';
    }
    cout << endl;
    
    i = 0, j = m - 1;
    for( i, j; j < n; j ++, i ++)
    {
        int maxv = -1e9;
        for(int t = i; t <= j; t ++)
        {
            maxv = max(maxv, a[t]);
        }
        cout << maxv << ' ';
    }
    

    return 0;
    
}

但是这种暴力做法在 k 逼近 n 时将会超时，所以需要进行优化

算法2

(单调队列优化滑动窗口) O(n)O(n)

可以考虑使用单调队列来对滑动窗口进行优化

我们考虑如何维护队列的单调性：

  • 由于每次窗口挪动仅会加入一个数字，去掉一个数字，我们可以在每次挪动窗口时进行队列的调整
  • 以维护最小值为例，在每次向窗口中加入新数字时，如果当前队尾的元素大于或等于新数字，那么其永远也不会被输出，且会在新数字被踢出队列前出队，因此我们就可以直接在队列中将其删掉
  • 这样，整个队列就变成了一个单调递增的队列，每次只需要输出队列的头部即可

这样优化之后，整个算法的时间复杂度可以降为 O(n)O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

using namespace std;

const int N = 1000010;
int n, m;
int a[N], q[N];

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