通过在 O(n) 或更短的时间内从列表中的任何索引开始，两只青蛙可以创建的最大距离？

Question

我想知道是否可以在 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 = array[i], array[i + 1]
        if next_height >= this_height:
            current_peak_index = i + 1
            if next_height == this_height:
                repeat_peaks += 1
            else:
                is_going_up = True
                if repeat_peaks > 0:
                    repeat_peaks = 0
        else:
            if is_going_up:
                previous_peak_index = current_peak_index - repeat_peaks
                is_going_up = False
                repeat_peaks = 0
            current_peak_index = i + 1
        max_distance = max(max_distance, current_peak_index - previous_peak_index)

    return max_distance

---

[编辑] 由于有人问过，这里是 O(n log n) 的 Python 实现：

def solution(array: list) -> int:
    """
    Solution that loops through every index in the array once and calculates the score based on max distance frogs
    can reach given the start index.
    """
    n = len(array)
    max_score = 0
    # we loop through each index
    for index in range(n):
        this_score = 0
        # we go as far as frog_1 can left
        for lj_index in range(index, 0, -1):
            if array[lj_index-1] < array[lj_index]:
                break
            else:
                this_score += 1
        # we go as far as frog_2 can right
        for rj_index in range(index, n-1):
            if array[rj_index+1] < array[rj_index]:
                break
            else:
                this_score += 1
        # we update our max_score variable to max(this_score, max_score)
        max_score = max(this_score, max_score)

    return max_score

Answer 1

这个问题可以在 O(n) 时间内回答。你只需要改变你看待问题的方式。它真的在问你，直方图中两个相邻峰值之间的最大距离是多少？

基本上，当您穿过阵列时，请记住之前的峰值。然后，对于您当前的位置，您要标记是要上坡还是下坡。如果你正在下降，那么继续下降直到你到达一个低谷，然后继续上升直到你到达一个高峰。然后找到这个峰值和前一个峰值之间的距离。最后，记住当前峰值为前一个峰值并继续。

我在下面用 C# 编写了一个解决方案，但这应该很容易翻译成 Python 或您选择的语言。

    class Solution
    {
        public int Solve(int[] arr)
        {
            // save the current height as the start of the array
            var currentHeight = arr[0];

            // max used to save the current maximum distance
            var max = 0;
            
            // the location of the previous peak that we detected. Start at index 0.
            var prevPeak = 0;

            // current location in the array
            var i = 0;

            // indicated if we are going up or down a slope.
            var goingUp = false;

            // this is used to save the location of the start of a peak; two adjacent
            // nodes with the same height could be at the peak.
            // we would want to make distance to be the start of this sequence
            var currentPeakStart = 0;


            while (i < arr.Length-1)
            {
                // if we are going down the slope and the current node is >= to the next node or
                // if we are going up the slope and the current node is <= to the next node then
                // keep moving along the array and save the height
                if ((!goingUp && currentHeight >= arr[i+1]) || (goingUp && currentHeight <= arr[i+1]))
                {
                    // if the current height == next height then 
                    // don't save the currentPeakStart as this peak started in a previous node.
                    if (goingUp && currentHeight < arr[i + 1])
                    {
                        currentPeakStart = i + 1;
                    }
                    currentHeight = arr[i + 1];
                    i++;
                }
                // if we are going down and the next node is higher than the current then we have reached a
                // valley in the histogram. we now need to make our way up to the next peak.
                else if (!goingUp)

                {
                    goingUp = true;
                }
                // if we are going up and the next node is now lower, this indicates we have reached the next peak.
                else if (goingUp)
                {
                    // distance between the current peak and previous peak.
                    var distance = i - prevPeak;
                    // save max
                    max = Math.Max(max, distance);

                    // if the start of the peak is not the current location, then override the prev peak as the start of the peak.
                    // this is the corner case for when you have muliple adjcent matching heights as the peak;
                    // [5, 5]. We don't want to save the second 5's location as the prev peak,
                    // we want the first location as the prevPeak.
                    if (i != currentPeakStart)
                    {
                        prevPeak = currentPeakStart;
                    }
                    else
                    {
                        prevPeak = i;
                    }

                    // reached peak so that means the next step is to walk down the slope.
                    goingUp = false;
                }
            }

            // final calculation as the last location in the histogram is the final peak.
            var d = i - prevPeak;
            max = Math.Max(max, d);

            return max;
        }
    }