@russrage
Я

Как оптимизировать код на Python?

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

На входе:
T - список дневных температур, значения температур от 30 до 100
На выходе:
массив с количеством дней

Пример:
T = [73, 74, 75, 71, 69, 72, 76, 73]
daysNumber( T ) --> [1, 1, 4, 2, 1, 1, 0, 0]
Реализуйте функцию daily_temperatures

t = [73, 74, 75, 71, 69, 72, 76, 73]


def daily_temperatures(lst):
    list_count = []
    for start_index in range(len(lst)):
        count = 0
        for letter in range(start_index + 1, len(lst)):
            if lst[letter] > lst[start_index]:
                count += 1
                list_count.append(letter - start_index)
                break
        if count == 0:
            list_count.append(0)
    return list_count


daily_temperatures(t)

Собственно, как оптимизировать это?
  • Вопрос задан
  • 292 просмотра
Решения вопроса 2
aRegius
@aRegius
Python Enthusiast
days = []

for ind, temp in enumerate(t):
	   temp_greater = next(((i, val) for i, val in enumerate(t[ind+1:], ind+1) if val > temp), 0)
	   day = temp_greater[0]-ind if temp_greater else 0
	   days.append(day)
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
У вас решение за O(N^2), когда как можно сделать решение за O(N). Тут не в питоне дело, а в плохом алгоритме.

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

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

Я не совсем питонист, но вот примерный код:

def days_till_warming(T):
    counts = []
    stack = []
    for i, curr_temp in enumerate(reversed(T)):
        while len(stack)>0 and stack[-1][0] <= curr_temp:
            stack.pop()
        delta = i - stack[-1][1] if len(stack) > 0 else 0
        stack.append([curr_temp, i])
        counts.append(delta)
    return list(reversed(counts))
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
adugin
@adugin Куратор тега Python
Один из вариантов "в лоб" (без использования допфункций типа takewhile):
def days_till_warming(T):
    counts = []
    for i, curr_temp in enumerate(T):
        for j, next_temp in enumerate(T[i+1:], i + 1):
            if next_temp > curr_temp:
                delta = j - i
                break
        else:
             delta = 0
        counts.append(delta)
    return counts
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
08 мар. 2021, в 13:42
1000 руб./в час
08 мар. 2021, в 12:56
2000 руб./за проект
08 мар. 2021, в 12:35
50000 руб./за проект