首页 > 试题广场 >

游游的最长稳定子数组

[编程题]游游的最长稳定子数组
  • 热度指数：1777 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}定义一个数组被称为稳定，当且仅当对于数组中任意相邻元素 a_i,a_{i+1}，都有 |a_{i+1}-a_i|\leqq 1。
\hspace{15pt}给定长度为 n 的整数数组 a，请你求出其最长稳定连续子数组的长度。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 10^{5}\right)——数组长度。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots ,a_n\left(1\leqq a_i\leqq 10^{9}\right)——数组元素。


输出描述:
\hspace{15pt}输出一个整数，表示最长稳定连续子数组的长度。
示例1

输入

5
2 4 2 3 2

输出

3

说明

子数组 [2,3,2] 满足稳定条件且长度最大。
算法知识视频讲解
添加回答
牛客682849269号头像 牛客682849269号
importjava.util.Scanner;
importjava.util.*;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
publicclassMain {
    publicstaticvoidmain(String[] args) {
        Scanner in = newScanner(System.in);
        intlast = 0;
        intcurrent = 0;
        intres = 0;
        intbest = 0;
 
        intn = in.nextInt();
        int[] arr = newint[n];   
 
        for(inti=0; i<n; i++) {
            current = in.nextInt();
            // System.out.print(current);
 
            if( Math.abs(current-last) <= 1) {
                    res += 1;
            }
            else{
                if(res > best) best = res;
                res = 0;
            }
            if(res > best) best = res;
 
            last = current;
        }
        System.out.println(best+1);
    }
}
发表于 2023-09-20 15:02:21 回复(0)
牛客487544150号头像 牛客487544150号 
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> aIntVec(n);
        for (int i = 0; i < n; i++) {
            cin >> aIntVec[i];
        }
        int maxLen = 0;
        int left,right;
        for (int i = 0; i < n; i++) {
            left = i;
            int _len = 1;
            for (int j = i+1; j < n; j++) {
                right = j;
                int _abs = std::abs(aIntVec[right] - aIntVec[left]);
                if (_abs <= 1) {
                    _len += 1;
                    left++; // update
                    if (right == n-1) {
                        maxLen = maxLen > _len ? maxLen : _len;
                        break;
                    }
                } else {
                    maxLen = maxLen > _len ? maxLen : _len;
                    i = i + _len - 1;
                    break;
                }
            }
        }
        cout << maxLen << endl;
    }
}

发表于 2025-12-14 11:28:27 回复(0)
代码怎么又不跑了头像 代码怎么又不跑了 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) nums[i] = in.nextInt();

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

            System.out.println(maxLen);
        }
    }
}

发表于 2025-12-06 16:07:37 回复(0)
Python3
三文鱼在发呆头像 三文鱼在发呆 
n = int(input())
num = list(map(int, input().split()))
left = 0
max_length = 0
length = 0
for i in range(1, n):
    if abs(num[i] - num[i-1]) <= 1:
        if length > max_length:
            max_length = length
        length = i - left + 2
    elif abs(num[i] - num[i-1]) > 1:
        left = i
        length = i - left + 2
print(max_length)

发表于 2025-10-27 18:24:34 回复(0)
C
人生有三乐头像 人生有三乐
#include <stdio.h>
#include <stdlib.h>
//双指针的时间复杂度基本都是O（n）吧，多往这方面想就行
//确实可以用双指针，一个指针指向子数组头部，一个指向尾部，当这个尾部指针找不到符合位置时就跳过这个数组去找下一个子数组即可。

int main() {
    int n;
    scanf("%d",&n);
    int array[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&array[i]);
    }

    int max_length=1;//初始化最长子数组长度
    int a=0,b=a+1;
    int temp_length=1; //记录临时的子数组长度
    while (b<n) {
       
        if (abs(array[b]-array[b-1])<=1) {   //小于则符合
            temp_length++; //长度加1
            b++;  //b移动到下一个位置
            if (temp_length>max_length) {  //记录最大长度
                max_length=temp_length;
            }
        }else {  //不符合则跳到下一个子数组重新找
            a=b;
            b=a+1;
            temp_length=1;
        }

       
    }

    printf("%d",max_length);
    return 0;
}
发表于 2025-10-19 14:48:49 回复(0)
bigqin头像 bigqin 
while True:
    try:
        n = int(input())
        nums = list(map(int, input().split()))
        

        left = -1
        indexLeft, length = 0, 0
        for i in range(n):
            if abs(left - nums[i]) <= 1:
                length = max(length, i - indexLeft + 1)
            else:
                indexLeft = i
            left = nums[i]
        print(length)

        
    except Exception as e:
        break

发表于 2025-09-11 22:05:52 回复(0)
Go
草海桐头像 草海桐 
package main

import (
    "fmt"
)

func Abs(a, b int) int{
    if a >b{
        return a-b
    }
    return b-a
}

func main() {
    var n int
    fmt.Scan(&n)
    var k = make([]int, n+1) // 多一个
    for i:=0;i<n;i++{
        fmt.Scanf("%d", &k[i])
    }
    k[n]=-2 // -2-0>1，确保k最后的稳定部分计算进去
    var left, right, max int = 0,1,1
    for right <= n{
        if Abs(k[right], k[right-1]) > 1{
            if max < right - left{
                max = right - left
            }
            left = right
            right++
        }else{
            right++
        }
    }
    fmt.Print(max)
}

发表于 2025-09-07 00:55:26 回复(0)
cxk5467头像 cxk5467
看了几个题解都不是很满意，自己写个算了。。。 
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (auto& num : nums)
    {
        cin >> num;
    }

    int max_len = 1;
    
    for (int l = 0, r = 1; r < n; ++r)
    {
        //r停留在第一个不符合要求的位置，r-l就是区间的长度
        while (r < n && abs(nums[r] - nums[r-1])<=1)
        {
            r++;
        }
        max_len = max(max_len, r-l);
        l = r;
    }
    cout << max_len;
    
}
// 64 位输出请用 printf("%lld")

发表于 2025-09-04 23:16:13 回复(0)
Java
六路折梅手头像 六路折梅手 
import java.util.*;
import java.io.*;

// 简单题，常规双指针定窗移动，不定窗口长度统计
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] input = Arrays.stream(bf.readLine().split(" ")).mapToInt(
                          Integer::parseInt).toArray();
        int maxLen = 1;
        //存储可变滑窗结果的数组
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(0);//初始添加首元素
        //两两比较后面与前一个元素来判断后面元素是否要添加
        for (int l = 0, r = 1; r < n; r++) {
            if (Math.abs(input[r] - input[l]) <= 1) {
                arr.add(r);
                if (arr.size() > maxLen) {
                    maxLen = arr.size(); //统计最长稳定连续子串长度
                }
            } else {
                arr.clear();
                arr.add(input[r]);
            }
            l++;
        }
        System.out.println(maxLen);
    }
}

发表于 2025-08-29 11:49:38 回复(0)
牛客847294653号头像 牛客847294653号
n = int(input())
a = list(map(int, input().split()))

max_length = 1  # 最小稳定子数组长度为1（单个元素）
current_length = 1  # 当前稳定子数组长度

for i in range(1, n):
    # 检查当前元素与前一个元素是否构成稳定对
    if abs(a[i] - a[i-1]) <= 1:
        current_length += 1
    else:
        # 不稳定，重置当前长度
        current_length = 1
   
    # 更新最大长度
    max_length = max(max_length, current_length)

print(max_length)
发表于 2025-08-27 10:20:52 回复(0)
Grandma_Wolf头像 Grandma_Wolf
#include <stdio.h>
#include <stdlib.h>
int cmp(int *arr,int width)
{
    int flag = 1;
    int temp = 1;
    for (int i = 1;i<width; i++)
    {
        if(abs(arr[i]-arr[i-1]) <= 1)
        {
            temp++;
            flag = temp>flag?temp:flag; //必须每一步都更新flag，因为如果整个数组都是稳定的，那么falg将得不到更新！！！！！
        }else
        {
            temp = 1;
        }
    }
   
    return flag;
}

int main()
{
    int arr[100000] = {0};
    int a = 0;
    scanf("%d",&a);
    for(int i = 0;i < a;i++)
    {
        scanf("%d",(arr+i));
    }
    printf("%d",cmp(arr,a));

    return 0;
}
发表于 2025-06-04 11:08:00 回复(0)
Java
suMMer5b头像 suMMer5b
有大佬成功解答了吗?为什么提交保存的时候测试样例第十道提示索引越界,样例参数也不给复制,没法复现啊
发表于 2023-07-13 23:50:28 回复(1)
提交观点

问题信息

双指针
难度：
12条回答 869浏览

热门推荐

相关试题

游游的最长稳定子数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号