滑动窗口的思想
首先暴力思考,就是定义两个指针i和j(j在后),枚举出每一个序列然后判断
但是,数组是满足单调性的
设当前区间[j,i]满足要求。i还需要回退吗?当然不!因为区间是单调递增的。
j呢?
设[j,i]是满足的最短序列,如果j回退,要么当前不是最短的,要么有重复数字,怎么都会产生矛盾
算法思想
同样设序列为[j,i]
先让i指针走,判断当前值是不是有重复
- 如果有,让j到i的位置,当前的单调序列不能要了,怎么要都是重复的
- 没有,更新区间长度并让i后移
y总的代码写的真的很漂亮,学习了
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10e5+10;
int a[N],Hash[N];
//hash存储区间内数字出现的次数
int n;
int ans;
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for(int i=0,j=0;i<n;i++)
{
Hash[a[i]]++;//记录当前数字出现的次数
while(Hash[a[i]]>1)、、出现了重复
{
Hash[a[j]]--;//j++前将先存储在序列中的数弹出
j++;
}
ans=max(ans,i-j+1);
}
cout<<ans<<endl;
return 0;
}