紫书 例题8-7 UVa 11572（滑动窗口）

滑动窗口这个方法名字非常形象， 先是窗口的右指针尽量往右滑， 滑不动了就滑窗口的左指针， 滑到右指针又可以开始滑动为止。

这道题是要记录滑的过程中最大的窗口长度， 限制条件是窗口中不能出现重复的值。

重复的值有两种判断方法。

一种是set， 其实就是开个vis数组， 但是数据有10的六次方， 数组肯定开不下， 所以用set来代替， 用时间换空间， set的查询是logn， 比数组要慢。

第二种是用map计算出一个last数组， 保存的是与当前数相同的前一个数的坐标。

两种方法大同小异。

set版

#include<cstdio>
#include<set>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 1123456;
int a[MAXN];

int main()
{
	int T, n;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		REP(i, 0, n) scanf("%d", &a[i]);
		
		set<int> s;
		int l = 0, r = 0, ans = 0;
		while(r < n)
		{
			while(r < n && !s.count(a[r])) s.insert(a[r++]);
			ans = max(ans, r - l);
			s.erase(a[l++]);
		}
		
		printf("%d
", ans);
	}
	
	return 0;	
} 

map版

#include<cstdio>
#include<map> 
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 1123456;
int a[MAXN], last[MAXN];
map<int, int> cur;

int main()
{
	int T, n;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		cur.clear();
		REP(i, 0, n) 
		{
			scanf("%d", &a[i]);
			if(!cur.count(a[i])) last[i] = -1;
			else last[i] = cur[a[i]];
			cur[a[i]] = i; 
		}
		
		int l = 0, r = 0, ans = 0;
		while(r < n)
		{
			while(r < n && last[r] < l) r++;
			ans = max(ans, r - l);
			l++;
		}
		
		printf("%d
", ans);
	}
	
	return 0;	
}