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

题目描述一个数组被称为稳定数组当且仅当对于任意相邻元素 ai​ 和 ai1​都满足 ∣ai1​−ai​∣≤1。给定一个长度为 n 的整数数组请你求出最长稳定连续子数组的长度。输入格式第一行整数 n(1≤n≤)第二行n 个整数 ai​(1≤ai​≤)输出格式输出一个整数表示最长稳定连续子数组的长度。解法思路这是一道一维数组遍历计数的基础题核心思路维护两个变量mx全局最长稳定子数组长度mxa当前正在统计的连续稳定长度遍历数组判断相邻元素是否满足稳定条件满足当前长度 1不满足更新最大值重置当前长度为 1遍历结束后必须再更新一次最大值时间复杂度O(n)空间复杂度O(n)代码实现#include bits/stdc.h using namespace std; int main() { int n,mx1; cin n; int a[100005]; for(int i1; in1; i) { cin a[i]; } int mxa1; int i1,j2; while(jn1) { if(abs(a[j] - a[i]) 2){ mxa; } else { mxmax(mx,mxa); mxa1; } 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、遍历结束最后更新最大值。