Максимальное число в последовательности гор

Question

Учитывая последовательность гор из n целых чисел, которые сначала увеличиваются, а затем уменьшаются, найдите вершину горы.

Пример

Учитывая числа = [1, 2, 4, 8, 6, 3] return 8

При заданных числах = [10, 9, 8, 7], return 10

class Solution:
     """
    @param nums: a mountain sequence which increase firstly and then decrease
    @return: then mountain top
    """
    def mountainSequence(self, nums):
        # write your code here
        if nums == []:
            return None
        if len(nums) <= 1:
            return nums[0]
        elif len(nums) <= 2:
            return max(nums[0], nums[1])


        for i in range(len(nums) -2):
            if nums[i] >= nums[i + 1]:
                return nums[i]
        return nums[-1]

он застрял на [3,5,3].Основываясь на моем анализе, после запуска цикла for все пошло не так.Но я не могу понять, почему цикл for не удался.

Answer 1

Это получит все триплеты из вашего ввода, изолирует все, что выше в середине, затем влево или вправо, и вернет тот, который самый высокий в целом:

def get_mountain_top(seq):
    triplets = zip(seq, seq[1:], seq[2:])

    tops = list(filter(lambda x: x[0] < x[1] > x[2], triplets))

    if tops:
        # max not allowed, leverage sorted
        return sorted(tops, key = lambda x:x[1])[-1]
        # return max(tops,key = lambda x:x[1])

    return None


print(get_mountain_top([1,2,3,4,3,2,3,4,5,6,7,6,5]))
print(get_mountain_top([1,1,1]))

Выход:

(6,7,6)
None

Не обрабатывает плато.

Доку:

• zip (), filter () и max ()

Answer 2

это должно быть более эффективно, чем ваш подход. это двоичный поиск, настроенный для вашего варианта использования:

def top(lst):
    low = 0
    high = len(lst)
    while low != high:
        i = (high+low)//2
        if lst[i] < lst[i+1]:
            low = i+1
        else:
            high = i
    return low

он начинается с середины списка и проверяет, увеличивается ли серия там. если это так, он устанавливает low и игнорирует все индексы ниже low для остальной части алгоритма. если ряд уже уменьшается, high устанавливается на текущий индекс, и все элементы выше игнорируются. и так далее ... когда high == low алгоритм завершается.

если у вас есть два или более одинаковых элемента в максимуме вашего списка (плато), алгоритм даже не прекратит работу.

и я пропустил тесты для пустых списков или списков длиной 1.