You need to enable JavaScript to run this app. 查找数组最大跌幅及给定Java实现代码的时间复杂度是多少
优惠活动
大模型
产品
解决方案
定价
更多

查找数组最大跌幅及给定Java实现代码的时间复杂度是多少

代码正确性判断
  • 存在多处逻辑错误,无法稳定输出正确结果:
    1. 差值计算逻辑有遗漏:仅处理了a[k]大于0和小于0的情况,漏了a[k]等于0的场景,此时temp不会被重新赋值,会复用历史值导致结果错误。且本质上a[i] - a[k]天然兼容a[k]正负、零的所有情况,拆分判断属于多余逻辑,反而增加了出错概率。
    2. 存在数组越界风险:循环中直接访问a[i+1],当i走到数组最后一个索引位置时,会触发数组越界异常。
    3. 无效判断:代码中else if (a[i] >= a[k] || a[i] <= a[k])的条件永远为真,等于没有做条件过滤,逻辑完全无意义。
    4. 测试用例验证不通过:你给出的第二个测试用例[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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.18 02:27:03