Поиск следующей большой элемент


Это дневные температуры проблема leetcode.com:

Приведенный список суточных температур, составить список, что за каждый день во входной, говорит вам, сколько дней вам придется подождать, пока температура теплее. Если нет будущего дня, для которых это возможно, поставить 0 вместо.

Например, с учетом температуры список= [73, 74, 75, 71, 69, 72, 76, 73], ваш выход должен быть [1, 1, 4, 2, 1, 1, 0, 0].

Примечание: длительность температуры будут в диапазоне [1, 30000]. Каждый температура будет целое число в диапазоне [30, 100].

Этот код работает для небольших входов, а не для списка длины 10,000. Что бы вы порекомендовали мне, чтобы изменить или улучшить в этом коде?

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        #O(n2)
        #max(temperatures)
        res=[]
        for i in range(len(temperatures)):
            cnt=0
            for j in range(i+1,len(temperatures)):
                cnt+=1
                if temperatures[i]<temperatures[j]:
                    res.append(cnt)
                    cnt=0
                    break
                elif j==len(temperatures)-1:
                    res.append(0)
                    cnt=0
                    break
        res.append(0)           
        return res


Комментарии
2 ответа

Начните с установки вашего res список с \$ 0 \$ значения. Таким образом:

res = [0] * len(temperatures)

Вам не понадобится elif состояние сейчас. Не нужно окончание res.append. Все res.append внутри цикла будут заменены res[i] = counter значения.

Использовать более описательные именования переменных, чем пропущены гласные (counter вместо cnt, result вместо res и т. д.)

Вы рассчитываете len(temperatures) в общей сложности \$ Н^2 \$ количество раз. Сохранить значение в другой переменной, а не.

Что касается сложности, ваш текущий алгоритм \$ o(п^2) \$, который может быть уменьшен с помощью более эффективного алгоритма. Взгляните на это так ответить , что делает использование ЛИФО очереди (стека) и получать результаты в \$ О(П) \$.

4
ответ дан 12 февраля 2018 в 06:02 Источник Поделиться

Сделайте РЭС список нулей. Также, сделать пустой список, который называется кэш. Это позволит сохранить показатели температуры в списке температуры.

res = [0] * len(temperatures)
cache = []

Процесс температура в обратном направлении.

for i in reversed(range(len(temperatures))):

Удалить кэшированные значения, которые меньше или равна температуре обработке. Убедитесь, что вы проверить, если список пуст. Они не нужны пока у вас есть температура, которая ближе к температурам, которые вы будете обрабатывать (помните, мы обрабатываем температуры в обратном) и теплее.

while cache and temperatures[i] >= temperatures[cache[-1]]:
cache.pop()

Так как этот цикл мог быть остановлен, потому что список пуст, проверьте, если список значений в нем. Затем добавить разницу между последнее кэшированное значение и индекс текущую температуру обработке в res. Если кэш пуст, мы знаем, нет будущего температурах выше, чем сейчас, поэтому нам не нужно изменять его, как это уже 0.

if cache:
res[i] = cache[-1] - i

Затем для каждой температуры кэш индекс температуре вы просто переработали.

cache.append(i)

2
ответ дан 12 февраля 2018 в 02:02 Источник Поделиться