小红的顺子

[题目链接](https://www.nowcoder.com/practice/76d6ca3612bd42a2900e540b511d2292)

思路

给定一个长度为 $n-1$ 的数组（是 $1$ 到 $n$ 的排列去掉一个数），要求找出最长的"顺子"——即一段连续子数组，满足相邻元素之差恰好为 $1$ （即 $a_{i+1} = a_i + 1$ ）。

一次遍历

这是一道经典的线性扫描题。用一个变量 $cur$ 记录以当前元素结尾的顺子长度：

如果 $a[i] = a[i-1] + 1$ ，说明当前元素可以接在前一个顺子后面， $cur$ 加 $1$ ；
否则，当前元素无法延续之前的顺子， $cur$ 重置为 $1$ 。

遍历过程中维护 $cur$ 的最大值即为答案。

样例演示

$n=5$ ，数组为 $[1, 2, 4, 5]$ ：

$i$	$a[i]$	是否接续	$cur$	$ans$
0	1	—	1	1
1	2	$2=1+1$ ✓	2	2
2	4	$4\neq2+1$ ✗	1	2
3	5	$5=4+1$ ✓	2	2

两段顺子 $[1,2]$ 和 $[4,5]$ ，最大长度为 $2$ 。

复杂度

时间复杂度： $O(n)$ ，一次遍历。
空间复杂度： $O(n)$ ，存储数组（若边读边处理可做到 $O(1)$ ）。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n-1);
    for(int i=0;i<n-1;i++) scanf("%d",&a[i]);
    int ans=1, cur=1;
    for(int i=1;i<n-1;i++){
        if(a[i]==a[i-1]+1) cur++;
        else cur=1;
        ans=max(ans,cur);
    }
    printf("%d\n",ans);
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n - 1];
        for (int i = 0; i < n - 1; i++) a[i] = sc.nextInt();
        int ans = 1, cur = 1;
        for (int i = 1; i < n - 1; i++) {
            if (a[i] == a[i - 1] + 1) cur++;
            else cur = 1;
            ans = Math.max(ans, cur);
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
m = len(a)
ans = 1
cur = 1
for i in range(1, m):
    if a[i] == a[i-1] + 1:
        cur += 1
    else:
        cur = 1
    ans = max(ans, cur)
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    let ans = 1, cur = 1;
    for (let i = 1; i < a.length; i++) {
        if (a[i] === a[i - 1] + 1) cur++;
        else cur = 1;
        ans = Math.max(ans, cur);
    }
    console.log(ans);
});