1. 例题分析

题目描述

给出 N 个整数，和一个长度值 Len ，要求在这 N 个整数中每个长度为 Len 的连续一段数中的最大值。

例如：N=8，Len=3，8个整数是： 2 5 1 1 2 4 7 1 。答案是 5 5 2 4 7 7 。

2 5 1 的最大值是 5
5 1 1 的最大值是 5
1 1 2 的最大值是 2
1 2 4 的最大值是 4
2 4 7 的最大值是 7
4 7 1 的最大值是 7

输入格式

第 1 行 2 个正整数：N , Len 。N 范围 [2...100000] ，Len 范围 [2...N];

第 2 行：N 个正整数，每个数范围 [1...1000000000]。

输出格式

一行，N-Len+1 个整数。

样例

10 5
7 2 1 4 3 8 5 4 3 2 1

7 8 8 8 8 8 5

我们先来解释一下样例数据，看看这个答案是怎么出来的。

也就是说，我们每次是比较 Len 个连续的数（就是橙色格子），从中选出最大值进行输出（最大值已经在最右列标注为绿色格子）。橙色格子的内容我们称为 滑动窗口，这窗口的内容一致在变。

有些同学看到题目之后，会觉得很容易，不就是循环刷最大值吗，然后写出了下面的代码：

#include<bits/stdc++.h>
using namespace std;
int x[100001]; 
int main()
{
	int MAX,i,j,n,len;
	scanf("%d%d",&n,&len);

	for(i=1;i<=n;i++)
		scanf("%d",&x[i]);

	for(i=len;i<=n;i++)
	{
		MAX = 0;
		for(j=i-len+1;j<=i;j++)
			MAX = max(MAX,x[j]);
		
		printf("%d ",MAX);
	}
	
	return 0;
}

上面这个代码是拿不到满分的，你试想一下如果 n = 100000, len = 50000 , 那么第一层循环要循环 50001 次，第二层循环要循环 50000 次，也就是说，两者乘起来，就是要循环 2.5*${10}^9$ , 一定超时的。所以，这条题的意思很清晰，但是有陷阱的，要拿满分有相当的难度，如何提高效率是解题的关键。

2. 解题突破口

假设 len 很大，那么上图中橙色的数字就是长长的一串，用笨方法就是逐一比较，要比较很多次。如何在这个环节中减少比较的次数，快速找到这串数字当中的最大值就是关键的突破方向。

1. 我们第一个要考虑的，就是是否有一些数字是 垃圾数字，我们把垃圾扔掉了，留下的数字越少，比较的次数就越少。

假设 len 是 5 ，有这么几个连续的数字：

7 2 1 4 3

这几个数字前面还有数字，后面也还有数字，只不过，在某个瞬间，橙色的数字就是这几个。我们试着去看看有那些数字是没用的。

• 我找到的第 1 个 没用的数字是 2 。因为 2 永远都不可能存在一个长度为 5 的滑动窗口的最大值 。这个 2 的前面是 7 ，如果滑动窗口包含了 7，2 就绝不可能是最大值，如果不包含 7，那就一定会包含后面的 4 ，所以 2 也不可能是最大值。反正，无论如何，这一个 2 是可以忽略的（如果其它位置有 2 ，要重新分析，此 2 非彼 2 ）。

• 我找到的第 2 个没用的数字是 1。原因也是类似的，前面有 2 和 7 ，如果不包含 7 和 2，那滑动窗口就一定会包含 后面的 4 , 这个 1没机会成为某个滑动窗口个的最大值。

• 接下来我们要讨论一下 3 。就从目前看到的这个 5 个数字来看，我没办法下结论说 3 就是没用的数字，假设 3 后面 连续来 4 个 1 （只要比 3 小的就行），那么在某个滑动窗口里面这个 3 就是最大的。

到了这里，我来做一个小归纳：

我们可以维护这一个活动窗口，这个活动窗口最多最多包含 len 个数字，随着时间的推移（下标 i 的变化），我们会活动窗口内的垃圾数据删除，留下来的数据都是有用的，而且高效的，删除数据的过程就是修剪

一个数字要能在活动窗口中存在，需要同时满足 2 个条件： 它的右边没有比它大的数字； 这个数字距离窗口当前数字(下标 i ）的距离不能超过 len-1

上面这两句话非常关键，很抽象，需要大家品味推敲。题意说了滑动窗口的长度是 len，所以，如果一个数虽然很大，但是已经距离循环变量 i 很远了，那么它再大我们也不会考虑，可以扔掉。一个数字可以很小，它只要是很新鲜的，因为说不定随着时间的推移，那些比它大的数字都过期被删掉，而它就会成为那个时候的顶梁柱，所以它可能会是明日之星，我们还是要保留。

2. 剩下来的这些数字少了之后，我们如何快速的定位到最大值？

满足上面的规则的情况下，这个滑动窗口里面的数字就是一个 递减数列，既然是递减数列，我们找当中的最大值很容易的，就是看数列里面的第一个数。

3. 从想法到算法

上面已经把这个规则说得很清晰了，下面就是在程序上如何来实现。

我们可以用一个单调队列来实现上面的内容。对于这条题来说，队列里面的内容就是一个单调下降的内容，我们通过图表来表示。

1. 维护着一个单调下降的队列，因为队列是单调下降的，所以最大值就是队头。

2. 维护单调下降队列的要点是：新来一个数的时候，把队尾那些比新来的数小的数字扔掉（出队列），然后再来把新来的数字入队

3. 队列左端的过期数据是要清理掉的。这里有两个办法来判断是否过期，第一个方法是用结构体，结构体里面包含这个数字的位置信息；第二个方法就是队列里面不放具体的数字，放的是下标。第 1 种方法容易理解，第二种方法更巧妙，高手喜欢后者。

4. 程序填空

1. 队列中存放结构体，结构体包含数据和位置信息

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int num,id;
};
node q[100001];
int head,tail,n,t,len;
int main()
{
	node temp;

	scanf("%d%d",&n,&len);

	head=tail=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t);
		
		//队尾端出队列，如果队尾的数字没有新来的数字 t 大，就没有存在的意义，出队列 
		while(tail>head&&__填空(1)__)
			__填空(2)__;
		
		//队首端出队列，如果队首的数字和新来的数字的距离（下标距离）超过 len，就是过期数据，出退了 
		while(tail>head&&__填空(3)__)
			__填空(4)__;
		
		temp.num = t;
		temp.id = i;
		q[tail++] = temp; // 新来的数据入队列 

		if(i>=len)	printf("%d ",__填空(5)__);
	}
	
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}