每日一题3.23——最长稳定连续子数组

题目描述

一个数组被称为稳定数组，当且仅当对于任意相邻元素 ai​ 和 ai+1​，都满足 ∣ai+1​−ai​∣≤1。

给定一个长度为 n 的整数数组，请你求出最长稳定连续子数组的长度。

输入格式

第一行：整数 n(1≤n≤)

第二行：n 个整数 ai​(1≤ai​≤)

输出格式

输出一个整数，表示最长稳定连续子数组的长度。

解法思路

这是一道一维数组遍历计数的基础题，核心思路：

1. 维护两个变量：
   • mx：全局最长稳定子数组长度
   • mxa：当前正在统计的连续稳定长度
2. 遍历数组，判断相邻元素是否满足稳定条件
3. 满足：当前长度 +1
4. 不满足：更新最大值，重置当前长度为 1
5. 遍历结束后必须再更新一次最大值

时间复杂度：O(n)

空间复杂度：O(n)

代码实现

#include <bits/stdc++.h> using namespace std; int main() { int n,mx=1; cin >> n; int a[100005]; for(int i=1; i<n+1; i++) { cin >> a[i]; } int mxa=1; int i=1,j=2; while(j<n+1) { if(abs(a[j] - a[i]) < 2){ mxa++; } else { mx=max(mx,mxa); mxa=1; } i++; j++; } mx = max(mx, mxa); cout << mx << endl; }

测试样例

样例输入：

5 1 2 2 3 1

样例输出：

4

代码关键点

• 初始值必须设为 1：单个元素本身就是稳定子数组，长度为 1。
• 遍历结束必须再更新最大值：避免最后一段连续稳定子数组被遗漏。
• 输入加速：面对 n=数据，需要加ios::sync_with_stdio(false);防止超时。

学到的知识点

• 双变量维护：用mxa记录当前连续稳定长度，mx记录全局最大值；
• 边界处理：初始值设为 1、遍历结束最后更新最大值。