题目链接

小红的顺子

题目描述

小红有一个长度为 的数组，满足 且 ，求顺子的最大长度。

顺子的定义为：对于长度为 的数组 ，如果 （），则称 是顺子。

输入:

  • 第一行一个整数 ，表示数组的长度加1
  • 第二行 个整数，表示严格递增的数组

输出:

  • 一个整数，表示顺子的最大长度

解题思路

这是一个序列问题，可以通过以下步骤解决：

  1. 首先理解题目特点：

    • 输入数组已经是严格递增的
    • 不需要排序和去重
    • 只需要找到连续递增（差值为1）的最长子序列

  2. 解题策略：

    • 直接遍历数组
    • 检查相邻两个数的差值是否为1
    • 维护最长的连续序列长度

  3. 具体步骤：

    • 遍历数组，检查相邻元素
    • 如果 ，则当前连续序列长度加1
    • 否则重新开始计数
    • 维护最大长度

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n - 1);
    for(int i = 0; i < n - 1; i++) {
        cin >> a[i];
    }
    
    int maxLen = 1;  // 最长顺子长度
    int curLen = 1;  // 当前顺子长度
    
    // 遍历寻找连续序列
    for(int i = 1; i < n - 1; i++) {
        if(a[i] == a[i-1] + 1) {
            curLen++;
            maxLen = max(maxLen, curLen);
        } else {
            curLen = 1;
        }
    }
    
    cout << maxLen << endl;
    return 0;
}

import java.util.*;

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 maxLen = 1;  // 最长顺子长度
        int curLen = 1;  // 当前顺子长度
        
        // 遍历寻找连续序列
        for(int i = 1; i < n - 1; i++) {
            if(a[i] == a[i-1] + 1) {
                curLen++;
                maxLen = Math.max(maxLen, curLen);
            } else {
                curLen = 1;
            }
        }
        
        System.out.println(maxLen);
    }
}

n = int(input())
a = list(map(int, input().split()))

max_len = 1  # 最长顺子长度
cur_len = 1  # 当前顺子长度

# 遍历寻找连续序列
for i in range(1, n - 1):
    if a[i] == a[i-1] + 1:
        cur_len += 1
        max_len = max(max_len, cur_len)
    else:
        cur_len = 1

print(max_len)

算法及复杂度

  • 算法：一次遍历
  • 时间复杂度： - 只需要遍历一次数组
  • 空间复杂度： - 需要存储输入数组