Container With Most Water

Q: Какова временная сложность задачи Container With Most Water?

Решение с двумя указателями работает за время O(n) и использует O(1) дополнительной памяти, поскольку на каждом шаге один указатель перемещается на одну позицию внутрь. Проверка каждой пары занимает O(n²), а сортировка линий по высоте — O(n log n).

Q: Зачем перемещать указатель к более короткой линии?

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

Q: Является ли задача «Контейнер с наибольшим количеством воды» жадной задачей?

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

СреднеДва указателя Жадные алгоритмы

+10

Дан список height неотрицательных целых чисел. Линия i — это вертикальная стена высотой height[i], расположенная в позиции i. Любые две линии вместе с землёй образуют контейнер, который вмещает столько воды, сколько равно высоте более короткой линии, умноженной на расстояние между двумя линиями. Остальные линии не мешают. Верните максимальное количество воды, которое может вместить одна пара линий.

Функция

maxArea(height: integer-array) → integer

heightinteger-array: высоты строк в позициях 0, 1, 2 и так далее
Возвращаетinteger: наибольшее количество воды, которое могут вместить две линии

Ограничения

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
Ответ не превышает 10⁸, поэтому помещается в 32-битное целое число.

Примеры

Ввод: height = [3, 7, 2, 5, 4, 7, 3, 6]
Вывод: 36
Пояснение: Линии на позициях 1 и 7 высотой 7 и 6 находятся на расстоянии 6 друг от друга и вмещают 6 × 6 = 36. Две самые высокие линии — высотой 7 на позициях 1 и 5 — вмещают только 7 × 4 = 28.

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

Здесь линии между двумя вашими линиями игнорируются. Если бы каждая линия была сплошной стеной, сколько воды скопилось бы между ними? Сможешь вычислить это тоже за O(n)?

Решение

Проверка всех n²/2 пар означает 5 × 10^7 вычислений произведения для 10^4 линий. Количество воды зависит только от более короткой линии в паре, поэтому, как только линия становится более короткой стороной самого широкого контейнера, который ещё можно образовать, ни один более узкий контейнер с её участием не сможет вместить больше воды. Два указателя превращают это в один проход с обоих концов.

Проверьте каждую пару

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

Идея

Пара i < j вмещает min(height[i], height[j]) × (j - i): вода переливается через более низкую стенку, а ширина дна равна j - i. Перебери все пары и оставь наибольшее значение.

Для n линий получается n(n-1)/2 пар: около 5 × 10^7 для 10^4 линий, и при каждом удвоении n их становится в четыре раза больше.

Алгоритм

Установи best равным 0.
Для каждого i и каждого j после него вычисли min(height[i], height[j]) × (j - i).
Сохрани большее из значений best и этого значения.
Верни best.

def maxArea(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            best = max(best, water)
    return best

Сначала самые высокие строки

Идея

Если линия i — более короткая сторона контейнера, её парой может быть любая линия не ниже неё. Поэтому наилучший такой контейнер образует пара этой линии с самой дальней линией, которая не ниже неё.

Расположим линии от самой высокой к самой низкой. Когда очередь доходит до линии i, все уже размещённые линии не ниже неё, а самая дальняя из них находится на крайнем левом или крайнем правом размещённом индексе — lo или hi. Поэтому линия i может образовать контейнер площадью не более height[i] × max(i - lo, hi - i), а наилучший контейнер учитывается, когда очередь доходит до его более короткой линии. Если две линии одинаковой высоты, то вторая размещённая видит первую как пару.

В первом примере линии высотой 7 на позициях 1 и 5 идут первыми и образуют контейнер площадью 28. Затем линия высотой 6 на позиции 7 видит lo = 1 и образует контейнер площадью 36. Сортировка требует времени O(n log n) и памяти O(n).

Алгоритм

Отсортируй индексы по высоте, от самой высокой к самой низкой.
Установи lo и hi в первый индекс в этом порядке, а best — в 0.
Для каждого следующего индекса i вычисли height[i], умноженную на большее из значений i - lo и hi - i, и сохрани наилучшее значение.
Обнови lo и hi, включив в них i.
Верни best.

def maxArea(height):
    # Indices from the tallest line to the shortest.
    order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
    lo = hi = order[0]  # leftmost and rightmost index among the lines placed so far
    best = 0
    for i in order[1:]:
        # Every placed line is at least as tall as line i, so line i is the
        # shorter side, and its best partner is the placed line farthest away.
        best = max(best, height[i] * max(i - lo, hi - i))
        lo = min(lo, i)
        hi = max(hi, i)
    return best

Два указателя с обоих концов

Идея

Начни с самого широкого контейнера: left = 0 и right = n-1, и предположим, что height[left] ≤ height[right]. Любой другой контейнер, в котором используется линия left, соединяет её с более близкой линией, поэтому он уже и не выше, чем height[left]. Ни один из них не вмещает больше воды, чем измеренное тобой количество, поэтому линия left больше не рассматривается, а left перемещается на один шаг вправо. При равной высоте больше не рассматриваются обе линии, поэтому можно переместить любую из них.

На каждом шаге исключается одна линия, поэтому указатели встретятся через n-1 шагов. Наилучшая пара никогда не будет пропущена: когда исключается первая из двух её линий, контейнер, измеренный в этот момент, вмещает как минимум столько же.

В первом примере позиции 0 и 7 вмещают 21, после чего исключается 3. Позиции 1 и 7 вмещают 36, после чего исключается 6. Остальные контейнеры вмещают 15, 28, 12, 10 и 2.

Алгоритм

Задай left = 0, right = n-1 и best = 0.
Пока left < right, вычисляй min(height[left], height[right]) × (right - left) и сохраняй наибольшее значение.
Если height[left] < height[right], сдвинь left на один шаг вправо. Иначе сдвинь right на один шаг влево.
Когда указатели встретятся, верни best.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line cannot do better with any line closer in, so drop it.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

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

Перемещение более высокой линии. В первом примере получается 21 вместо 36: линия высотой 6 на позиции 7 уходит раньше, чем встречается с линией высотой 7 на позиции 1.
Использование более высокой линии или среднего значения двух линий в качестве высоты. Вода переливается через более низкую стенку, поэтому высота — это минимум.
Измерение ширины как j - i + 1. Линии на позициях i и j находятся на расстоянии j - i друг от друга, поэтому [4, 4] вмещает 4, а не 8.
Предположение, что ответ определяется самыми высокими линиями или крайними линиями. В первом примере две линии высотой 7 вмещают 28, а крайняя пара — 21, тогда как ответ равен 36.

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

Какова временная сложность задачи Container With Most Water?

Решение с двумя указателями работает за время O(n) и использует O(1) дополнительной памяти, поскольку на каждом шаге один указатель перемещается на одну позицию внутрь. Проверка каждой пары занимает O(n²), а сортировка линий по высоте — O(n log n).

Зачем перемещать указатель к более короткой линии?

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

Является ли задача «Контейнер с наибольшим количеством воды» жадной задачей?

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

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

Тест #1

Тест #2

Аргумент

height = [3, 7, 2, 5, 4, 7, 3, 6]

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

Container With Most Water

Функция

Ограничения

Примеры

Подсказки

Решение

Проверьте каждую пару

Сначала самые высокие строки

Два указателя с обоих концов

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

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

Похожие задачи