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

算法改进

在上一题中，我们基于结构体实现了单调队列。队列中每一个成员都携带了两个信息：数字的值(num)，对应的下标(id)。

可以进一步改进，让队列值存放原来数组的下标，有了下标，就能获得对应的值。这就避免了重复的数据（既占时间，又占内存）。这种做法，被广泛的使用。如果考试遇到填空题，基本上都是这样写的。所以，如果要应对第一轮的理论题，必须要学会这个方法。

#include<bits/stdc++.h>
using namespace std;
int x[100001],q[100001]; // q 是队列，存放的是下标 
int head,tail,i,n,len;
int main()
{
	scanf("%d%d",&n,&len);
	for(i=1;i<=n;i++)
		scanf("%d",&x[i]);

	head=tail=1; // 空队列，左闭右开 
	for(i=1;i<=n;i++)
	{
		//队尾出队列，队尾的数字如果没有新来的数字 t 大，就队尾出队列 
		while(tail>head&&__填空(1)__)
			__填空(2)__;
		
		//队首出队列，如果队首的数字和当前新来数字的下标差距超过 len，就是过期数据，就队首出队列 
		while(tail>head&&__填空(3)__)
			__填空(4)__;
		
		//入队列，队列中存放的是下标 
		q[tail++] = i;

		if(i>=len)	printf("%d ",__填空(2)__);
		// 队列长度不够 len 的时候不输出 
	}
	
	return 0;
}

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

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

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

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

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