codeforce每日一题
题目链接
题目分数:1400
题目描述
输入 $n(2≤n≤1e5)$ 和长为 $n$ 的数组 $a(1≤a[i]≤1e5$ 且 $abs(a[i]-a[i-1])≤1)$。
输出 $a$ 的最长连续子数组的长度,满足数组中的最大值减最小值不超过 $1$。
样例
输入样例1
5
1 2 3 3 2
输出样例1
4
输入样例2
11
5 4 5 5 6 7 8 8 8 7 6
输出样例2
5
算法
(双指针) $O(n)$
我们发现满足条件的区间只能包含两个不同的元素,于是我们可以使用双指针去做,用一个数组维护当前去区间里的元素种类及个数,当右指针向右移动一格时,如果发现当前区间的元素个数大于$2$个,左指针就向右移动直到区间元素种类等于$2$为止。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
vector<int> w(n), s(100010, 0);
rep(i, 0, n - 1) cin>>w[i];
int cnt = 0;
int res = 0;
for(int i=0,j=0;i<n;i++)
{
if(s[w[i]]==0) cnt++;
s[w[i]]++;
while(cnt>2) if(--s[w[j++]] == 0) cnt--;
res = max(res, i - j + 1);
}
cout<<res<<endl;
return 0;
}
Java 代码
// https://www.acwing.com/blog/content/34755/
import java.util.*;
public class Main{
public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f;
public static void solve()
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] w = new int[n];
int[] s = new int[100010];
for(int i=0;i<n;i++) w[i] = sc.nextInt();
int cnt = 0, res = 0;
for(int i=0,j=0;i<n;i++)
{
if(s[w[i]] == 0) cnt++;
s[w[i]]++;
while(cnt > 2) if(--s[w[j++]] == 0) cnt--;
res = Math.max(res, i - j + 1);
}
System.out.println(res);
}
public static void main(String[] args)
{
solve();
}
}
Python 代码
# https://www.acwing.com/blog/content/34755/
def solve():
n = int(input())
w = [int(i) for i in input().split()]
s = [0] * 100010
res, cnt, j = 0, 0, 0
for i in range(n):
if s[w[i]] == 0: cnt += 1
s[w[i]] += 1
while cnt > 2:
s[w[j]] -= 1
if s[w[j]] == 0: cnt -= 1
j += 1
res = max(res, i - j + 1)
print(res)
def main():
solve()
if __name__ == '__main__':
main()