题目描述

不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来，作为礼物送给在南方的同学们。一共有 n 个时刻，给出每个时刻下落雪花的形状，用不同的整数表示不同的形状。在收集的过程中，同学们不希望有重复的雪花。你可以从任意 a 时刻开始，在 b 时刻停止。a 到 b 时刻中间的雪花也都将被收集。他们希望收集的雪花最多。

输入格式

第一行一个正整数 n；

第 2 行 n 个非负整数表示 n 个时刻雪花的形状。

输出格式

最多能收集雪花的数量。

样例

输入

5
1 2 3 2 1

输出

3
数据范围与提示
对于 97 分的数据，$1\le n\le 10^6,0\le x_i\le 10^8$。（为原始数据）

应用户要求，加入 3 分的数据，$1\le n\le 10^6,0\le x_i\le 10^9$。

分析

老水题了，使用unordered_set即可，在此给出相关用法：
笔者在此说明一下unordered_set是C++标准库中的一种关联容器，它提供了一种无序、唯一值的集合。使用HASH技术实现：

1. emplace：在集合中插入一个新元素。该函数的参数是要插入的元素。
2. count：返回集合中特定元素的个数。由于unordered_set中的元素是唯一的，所以该函数的返回值只能是0或1。
3. erase：从集合中删除一个元素。该函数的参数可以是元素本身或者迭代器指向的位置（笔者先不讨论迭代器），它会将匹配到的元素从集合中删除。

下面的了解即可，代码中未使用

4. empty：检查集合是否为空。当集合中没有任何元素时，该函数返回true；否则返回false。与很多容器相似
5. size：返回集合中元素的数量，并以整数形式返回。

代码

#include<bits/stdc++.h>
using namespace std;
int a,n,ans=0;
queue<int> q;
unordered_set<int> aa;
int main(){
	cin>>n;
	for (int i=1;i<=n;i++) {
		scanf("%d",&a);
		if (aa.count(a)==1) {
			while (!q.empty()){
				int tmp=q.front();q.pop();aa.erase(tmp);
				if (tmp==a) break;
			}
		}
		aa.emplace(a);
		q.push(a);
		ans=max(ans,(int)q.size());
	}
	cout<<ans;
	return 0;
}

分析

#include<bits/stdc++.h>
using namespace std;
int a,n,ans=0;
queue<int> q;
unordered_set<int> aa;

a 是当前时刻下落的雪花形状，n 是时刻的总个数，ans 是最终结果的变量。q 是一个队列，用于存储当前正在收集的雪花形状，aa 是一个哈希集合，用于存储已经出现过的雪花形状。（判重）

int main(){
	cin>>n;
	for (int i=1;i<=n;i++) {
		scanf("%d",&a);
		if (aa.count(a)==1) {
			while (!q.empty()){
				int tmp=q.front();q.pop();aa.erase(tmp);
				if (tmp==a) break;
			}
		}
		aa.emplace(a);
		q.push(a);
		ans=max(ans,(int)q.size());
	}
	cout<<ans;
	return 0;
}

1. 读入时刻的总个数 n。
2. 通过一个循环遍历每个时刻下落的雪花形状。使用 scanf("%d",&a) 读入当前时刻的雪花形状。
3. 接下来进行判断，如果这个雪花形状已经出现过（即哈希集合 aa 中已经存在该元素），则需要将队列中已经收集的、从头开始直到遇到重复形状的雪花形状都弹出队列，并从集合 aa 中删除对应的元素。然后将当前雪花形状加入集合 aa 中，并将其压入队列。最后更新最大收集数量 ans，即为队列的大小。最后输出结果 ans。