题解 | #游游的最长稳定子数组#

题目链接

游游的最长稳定子数组

题目描述

给定一个长度为 $n$ 的整数数组 $a$ 。一个数组被称为“稳定”的，当且仅当对于数组中任意相邻的两个元素 $a[i]$ 和 $a[i+1]$ ，都满足 $|a[i] - a[i+1]| \le 1$ 。

任务是求出给定数组 $a$ 的最长稳定连续子数组的长度。

解题思路

这是一个求解满足特定局部性质的最长连续子数组的问题。我们可以通过一次线性扫描来解决，这种方法通常也被看作是一种简单的动态规划。

我们的核心思路是，在遍历数组的同时，维护当前以第 $i$ 个元素结尾的最长稳定子数组的长度。

算法步骤如下：

初始化：
- $max\_len = 1$ ，用于记录全局的最长稳定子数组长度。任何单个元素的子数组都是稳定的，所以长度至少为 1（除非数组为空）。
- $current\_len = 1$ ，用于记录以当前元素结尾的稳定子数组的长度。
遍历数组：
- 从数组的第二个元素（下标为 1）开始，遍历到末尾。
- 在每一步，我们比较当前元素 $a[i]$ 和它前一个元素 $a[i-1]$ 。
- 如果 $|a[i] - a[i-1]| \le 1$ ：这意味着稳定性质得以延续。当前元素 $a[i]$ 可以接在以上一个元素结尾的稳定子数组后面，形成一个更长的稳定子数组。因此，我们将 $current\_len$ 加 1。
- 如果 $|a[i] - a[i-1]| > 1$ ：这意味着稳定性质被破坏。一个新的稳定子数组必须从当前元素 $a[i]$ 开始。因此，我们将 $current\_len$ 重置为 1。
更新全局最长长度：
- 在每次更新（或重置） $current\_len$ 之后，我们都需要用它来更新全局的 $max\_len$ ： $max\_len = \max(max\_len, current\_len)$ 。
处理边界情况：
- 如果输入的数组长度 $n$ 为 0，最长长度应为 0。
- 如果 $n > 0$ ，最长长度至少为 1。我们的初始化已经覆盖了这一点。

遍历结束后， $max\_len$ 中存储的就是最终的答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int max_len = 1;
    int current_len = 1;
    for (int i = 1; i < n; ++i) {
        if (abs(a[i] - a[i - 1]) <= 1) {
            current_len++;
        } else {
            current_len = 1;
        }
        max_len = max(max_len, current_len);
    }

    cout << max_len << endl;

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n == 0) {
            System.out.println(0);
            return;
        }

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int maxLen = 1;
        int currentLen = 1;
        for (int i = 1; i < n; i++) {
            if (Math.abs(a[i] - a[i - 1]) <= 1) {
                currentLen++;
            } else {
                currentLen = 1;
            }
            maxLen = Math.max(maxLen, currentLen);
        }

        System.out.println(maxLen);
    }
}

n = int(input())
if n == 0:
    print(0)
else:
    a = list(map(int, input().split()))
    max_len = 1
    current_len = 1
    for i in range(1, n):
        if abs(a[i] - a[i - 1]) <= 1:
            current_len += 1
        else:
            current_len = 1
        max_len = max(max_len, current_len)
    print(max_len)

算法及复杂度

算法：线性扫描（或简单动态规划）。
时间复杂度： $O(n)$ ，因为我们只对数组进行了一次遍历。
空间复杂度： $O(n)$ ，主要用于存储输入的数组。