我想知道是否可以在 O(n) 或更短的时间内完成这个挑战。描述如下：
青蛙跳
2 只青蛙可以从给定的 input_array 中的任何索引开始。该函数应该返回这些青蛙可以在它们之间创建的最大可能距离（两者的索引值之间的差异），让它们彼此跳得更远。
青蛙只能跳到更高值的元素或一些相同高度的元素上，它们不能跳过任何元素。
输入：[1, 5, 5, 2, 6]
输出：3。最大距离 3 是通过生成位置 3（0 索引）和左青蛙跳到索引 1 和右青蛙跳到索引 4 来创建的。
len(input_array) 介于 2 和 200 000 之间。数组中的值是介于 1 和 1 000 000 000 之间的整数。
实际上，这里的挑战似乎是找到最长的连续子序列，使其首先不增加，然后不减少（行为的变化点是开始索引）。这似乎是最高和子阵列任务的变体。
我最好的解决方案是 O(n log n) 通过迭代数组中的所有索引并携带一个max_value来检查两只青蛙可以从该迭代的索引跳多远。
这可以在 O(n) 或更少的时间复杂度内完成吗？
[解决] 谢谢大家的回复。这是一次性解决方案的 Python 实现：
def one_pass_solution(array: List[int]) -> int:
current_peak_index = 0
previous_peak_index = 0
repeat_peaks = 0
max_distance = 0
is_going_up = False
for i in range(len(array) - 1):
this_height, next_height …