Java查找连续非递减子数组 无额外数组约束下的逻辑问题排查
问题代码核心缺陷
- 判断逻辑完全偏离需求:原代码用数组首元素
arr[0]和后续元素做大小比较,未按要求判断相邻元素的非递减关系,从根源上无法识别正确的连续子序列边界 - 缺少断点处理逻辑:遇到相邻元素不满足非递减关系时,没有重置当前序列的计数和起点,导致跨断点的元素被错误拼接进最终结果,出现
[3,4,6,6,7]的错误输出 - 未适配“禁止使用额外数组”的约束:所有中间状态需通过临时整数变量记录,不得新建数组、集合类结构存储中间结果
无额外开销的实现方案
- 遍历数组时仅用临时整数变量记录两个关键状态:当前连续非递减序列的起点位置、全局最长序列的起止下标
- 每轮循环仅对比相邻的两个元素
arr[i]与arr[i+1]:若arr[i] > arr[i+1]说明连续序列中断,直接将当前序列起点重置为i+1即可 - 每轮循环实时计算当前片段的长度,与已记录的最长序列长度做对比,更长就更新全局最长序列的下标,遍历结束后直接根据下标从原数组读取元素输出,完全不产生额外数组开销
修正后可运行代码
public static void findLongestNonDecreasingSubarray(int arr[], int size) { int maxStart = 0, maxEnd = 0; int curStart = 0; for (int i = 0; i < size - 1; i++) { // 相邻元素不满足非递减,重置当前连续序列起点 if (arr[i] > arr[i + 1]) { curStart = i + 1; } // 计算当前片段长度,更新全局最长序列记录 int curLen = i + 1 - curStart + 1; int maxLen = maxEnd - maxStart + 1; if (curLen > maxLen) { maxStart = curStart; maxEnd = i + 1; } } // 直接基于原数组下标输出结果 System.out.print("匹配的连续非递减序列为 ["); for (int i = maxStart; i <= maxEnd; i++) { System.out.print(arr[i]); if (i < maxEnd) System.out.print(", "); } System.out.println("]"); System.out.println("序列长度: " + (maxEnd - maxStart + 1)); } public static void main(String[] args) { int arr[] = {5, 3, 6, 4, 6, 6, 7, 5}; int n = arr.length; findLongestNonDecreasingSubarray(arr, n); }
对给定测试数组运行上述代码,输出结果为[4, 6, 6, 7],序列长度为4,与目标要求完全匹配。
内容的提问来源于stack exchange,提问作者some_cs_student
相关产品推荐
相关产品推荐

