Leaders in an Array

+10

Дан массив целых чисел nums. Элемент является лидером, если он больше или равен каждому элементу справа от него. Справа от последнего элемента ничего нет, поэтому он всегда является лидером. Верни все лидеры в том порядке, в котором они встречаются в nums, слева направо.

Функция

leaders(nums: integer-array) → integer-array

numsinteger-array: массив целых чисел для поиска
Возвращаетinteger-array: лидеры nums, слева направо

Ограничения

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

Примеры

Ввод: nums = [12, 5, 9, 3, 6, 2]
Вывод: [12, 9, 6, 2]
Пояснение: 2 стоит последним, поэтому он начинает. 6 побеждает стоящую после него 2, 9 побеждает 3, 6 и 2, а 12 побеждает всех. 5 проигрывает 9, а 3 проигрывает 6, поэтому ответ — [12, 9, 6, 2].

Дополнительный вопрос

Если значения поступают по одному и после каждого нужно сообщать лидеров на данный момент, как обновлять список за амортизированное время O(1) на каждое значение?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Если читать слева направо, каждому элементу требуется заново просканировать суффикс. Идите справа налево: единственное, что нужно знать о суффиксе, — его наибольшее значение, и для него достаточно одной переменной. Так проверка за O(n²) превращается в один проход.

Проверьте всё справа

Верно, но не успевает на самых больших тестах

Идея

Примените определение: для каждого индекса i просматривайте следующие элементы и остановитесь на первом, который строго больше nums[i]. Если просмотр доходит до конца, nums[i] является лидером. Индексы проверяются слева направо, поэтому лидеры получаются в исходном порядке. В [12, 5, 9, 3, 6, 2] просмотр для 5 останавливается на 9, а для 3 — на 6.

Затраты связаны с просмотрами, которые доходят до конца. Если после 24,999 одинаковых значений следует одно большее, каждый элемент проходит почти весь массив: примерно 25,000 × 25,000 / 2, то есть более 3 × 10^8 сравнений.

Алгоритм

Создайте пустой список результатов.
Для каждого индекса i просматривайте j от i + 1 до конца.
Если какое-либо значение nums[j] больше, чем nums[i], остановитесь: nums[i] не является лидером.
Если такого j нет, добавьте nums[i] в результат.
Верните результат.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Один проход справа налево с отслеживанием максимума

Идея

Быть не меньше каждого элемента справа — то же самое, что быть не меньше их максимума. Двигаясь справа налево, можно поддерживать актуальное значение этого максимума. Последний элемент является лидером и задаёт начальный максимум. Каждый элемент левее становится лидером, если он не меньше текущего максимума, и тогда становится новым максимумом; иначе справа от него есть большее значение.

Для [12, 5, 9, 3, 6, 2]: лидером становится 2, затем 6, затем 9, затем 12, а 3 и 5 меньше максимума. Получился список [2, 6, 9, 12]; в обратном порядке это и будет ответ.

Каждый элемент сравнивается один раз: время O(n) и дополнительная память O(1), не считая результата. Версия на R отмечает лидеров в векторе logical(n), поэтому дополнительная память составляет O(n).

Алгоритм

Поместите последний элемент в результат и присвойте ему значение best.
Перемещайте i от предпоследнего индекса до 0.
Если nums[i] ≥ best, добавьте nums[i] в результат и присвойте ему значение best.
Разверните результат, чтобы лидеры располагались слева направо, и верните его.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Ловушки и крайние случаи

Использование > вместо ≥ при сравнении с текущим максимумом. В [4, 7, 7, 1, 7] каждый элемент 7 является лидером, но строгое сравнение оставляет только последний.
Начало с максимума 0 вместо последнего элемента. Для [-1, -5] нужно вернуть оба элемента, но максимум 0 исключает их.
Возврат лидеров в порядке их обнаружения: [2, 6, 9, 12] вместо [12, 9, 6, 2].
Добавление последнего элемента дважды из-за того, что цикл начинается с последнего индекса после того, как этот элемент уже добавлен в результат.
Сравнение каждого элемента только с соседним. В [5, 3, 9] число 5 больше соседнего с ним числа 3, но из-за 9 ответ — [9].

Частые вопросы3

Какова временная сложность поиска лидеров в массиве?

O(n) за один проход справа налево, потому что каждый элемент сравнивается с текущим максимумом один раз. Проверка каждого элемента относительно всех элементов справа от него в худшем случае требует O(n²), например, когда все значения равны.

Последний элемент всегда является лидером?

Да. Элемент-лидер должен быть не меньше каждого элемента справа от него, а у последнего элемента таких элементов нет, поэтому условие выполняется без дополнительных проверок.

Считаются ли равные значения лидерами?

Здесь — да: лидер должен быть больше или равен каждому элементу справа от него, поэтому в [4, 7, 7, 1, 7] все три семёрки являются лидерами. В некоторых версиях требуется строгое неравенство; тогда сравнивай с помощью >, и лидером будет только последнее из равных значений.

def leaders(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

nums = [12, 5, 9, 3, 6, 2]

Ожидаемый вывод

[12, 9, 6, 2]