Я пытаюсь решить вопрос LeetCode, где нужно узнать площадь емкость с наибольшим количеством воды. Я создал решение, которое, похоже, работает в моем тестировании, но оно не работает из-за того, что работает слишком медленно, когда я пытаюсь отправить его на LeetCode.
Моя идея состоит в том, что я создаю словарь кортежей (x, y) из входного списка, а затем для каждого элемента мне нужно найти максимальное расстояние до любой из других строк, которые равны или выше, чем он, и отсюда я могу вычислить, что максимальная площадь возможна для этой линии.
Как еще я могу подойти к этому, чтобы заставить его работать быстрее? (Я не могу успешно отправить решение, поэтому не вижу примеров ответов других пользователей)
def max_area(height) -> int:
areas = []
coords = {x: (x, y) for x, y in enumerate(height)}
for x in coords:
higher = [k for k in coords if coords[k][1] >= coords[x][1]]
area = max(abs(coords[j][0] - coords[x][0]) for j in higher) * coords[x][1]
areas.append(area)
return max(areas)
2 ответа
Ваш вопрос заставил меня тоже попробовать. Решение получилось очень похоже на псевдокод, предложенный @Marc, и Python, конечно, в любом случае довольно близок по удобочитаемости. Приведенный ниже код проходит на сайт и запускается (между запусками есть некоторые отклонения) быстрее, чем c. 95% и с меньшим использованием памяти, чем c. 75% решений. Код содержит комментарии в соответствующих позициях. Там же объясняются две дополнительные оптимизации.
def max_area(height: list[int]) -> int:
n = len(height) - 1
l = 0 # Index for left bar
r = n # Index for right bar
max_area = 0
while True:
# Give readable names:
left = height[l]
right = height[r]
# Current area, constrained by lower bar:
area = min(left, right) * (r - l)
if area > max_area:
# Keep tabs on maximum, the task doesn't ask for any
# more details than that.
max_area = area
# Move the smaller bar further inwards towards the center, expressed
# as moving left, where *not* moving left implies moving right.
# The smaller bar constrains the area, and we hope to get to a longer
# one by moving inwards, at which point the other bar forms the constraint,
# so the entire thing reverses.
move_left = left < right
# Instead of only moving the smaller bar inward by one step, there's two
# extra steps here:
# 1. While moving the smaller bar inward, skip all bars that are
# *even smaller*; those are definitely not the target, since both
# their height and horizontal delta will be smaller.
# 2. While skipping all smaller bars, we might hit the other bar:
# there is a 'valley' or at least nothing higher in between.
# Any more moving inwards would be a wasted effort, no matter the
# the direction (from left or right). We can return the current
# max. area.
#
# In the best case scenario, this may skip us right to the solution,
# e.g. for `[10, 1, 1, 1, 1, 1, 10]`: only one outer loop is necessary.
#
# Both loops look very similar, maybe there's room for some indirection
# here, although a function call would probably mess with the raw
# performance.
if move_left:
while height[l] <= left:
if l == r:
return max_area
l += 1
else:
while height[r] <= right:
if r == l:
return max_area
r -= 1
# Examples from the site
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49)
print(max_area([2, 3, 10, 5, 7, 8, 9]) == 36)
print(max_area([1, 3, 2, 5, 25, 24, 5]) == 24)
Что касается вашего кода:
Отображение
coords = {x: (x, y) for x, y in enumerate(height)}кажется довольно странным. Вы вроде картографирования
xсебе. Я бы сказал, что для решения проблемы гораздо проще не лечитьxв качествеxв смысле «двухмерного математического графика», но так жеiв смысле индекса массива. Это избавляет нас от необходимости даже объявлятьx, мы можем просто выполнить итерацию, используяi.Ты используешь
maxдважды, что каждый раз является операцией линейного поиска. Это излишне дорого, но, вероятно, не является узким местом.Любой алгоритм, основанный на нахождении, например все расстояния до каждого другого объекта за каждый предмет имеет взрывную сложность. Вероятно, это узкое место.
Мое предложение о вашем текущем решении:
def max_area(height) -> int:
areas = []
coords = {x: (x, y) for x, y in enumerate(height)}
for x in coords:
higher = [k for k in coords if coords[k][1] >= coords[x][1]]
area = max(abs(coords[j][0] - coords[x][0]) for j in higher) * coords[x][1]
areas.append(area)
return max(areas)
- Следите за самой большой областью на данный момент, вместо того, чтобы использовать список
areas.
def max_area(height) -> int:
coords = {x: (x, y) for x, y in enumerate(height)}
result = 0
for x in coords:
higher = [k for k in coords if coords[k][1] >= coords[x][1]]
area = max(abs(coords[j][0] - coords[x][0]) for j in higher) * coords[x][1]
result = max(result, area)
return result
Это уменьшает использование памяти, но этого недостаточно для решения задачи.
Решение можно считать методом грубой силы, которого обычно недостаточно для решения средних / сложных задач на LeetCode.
Ограничение $ п <= 3 * 10 ^ 4 $, куда $ n $ — длина входного списка. Как правило, с таким ограничением следует искать решение с временной сложностью меньше, чем $ O (п ^ 2) $.
Рассмотрим пример на LeetCode, где список ввода:
- высота = [1,8,6,2,5,4,8,3,7]
Для каждых двух столбцов самая большая площадь определяется самой нижней полосой. В этом примере две полосы 8 и 7, поэтому площадь 7 * (8 - 1) = 49. Обратите внимание, что (8 - 1) — разница между индексами баров. Это $ O (п) $ алгоритм:
Initialize l to 0
Initialize r to the right most index
Initialize max_area to 0
while l is lower than r
find the area as: lowest bar * (r - l)
update max_area
increment l if points to the lower bar, else decrement r
return max_area
В следующий раз вы можете проверить «подсказки» и вкладку «Обсудить», чтобы получить помощь или альтернативные решения.