查找数组最大跌幅及给定Java实现代码的时间复杂度是多少
代码正确性判断
- 存在多处逻辑错误,无法稳定输出正确结果:
- 差值计算逻辑有遗漏:仅处理了
a[k]大于0和小于0的情况,漏了a[k]等于0的场景,此时temp不会被重新赋值,会复用历史值导致结果错误。且本质上a[i] - a[k]天然兼容a[k]正负、零的所有情况,拆分判断属于多余逻辑,反而增加了出错概率。 - 存在数组越界风险:循环中直接访问
a[i+1],当i走到数组最后一个索引位置时,会触发数组越界异常。 - 无效判断:代码中
else if (a[i] >= a[k] || a[i] <= a[k])的条件永远为真,等于没有做条件过滤,逻辑完全无意义。 - 测试用例验证不通过:你给出的第二个测试用例
[5, 21, 3, 22, 12, 7, 26, 14],这段代码无法输出正确结果18。
- 差值计算逻辑有遗漏:仅处理了
实际时间复杂度
你的代码时间复杂度为O(N²),并不是你以为的O(N):
每次i指针向前移动1位后,k指针都会被重置到数组末尾,重新从末尾遍历到i的位置。最坏情况下(比如数组严格递减),总遍历次数为N + (N-1) + (N-2) + ... + 1 = N*(N+1)/2,完全符合平方级时间复杂度的特征。
正确O(N)实现思路
想要达到O(N)时间复杂度,只需要从右向左遍历数组,全程维护当前遍历位置右侧的最小值,每遍历到一个元素就计算「当前元素 - 右侧最小值」,同步更新最大差值即可。全程只需要遍历一次数组,额外空间复杂度为O(1)。
内容的提问来源于stack exchange,提问作者or regev
相关产品推荐
相关产品推荐

