В этой статье мы решим задачу #11 — Container with most water с LeetCode. Подходить к решению задачи будем итеративно: напишем перебор и будем его оптимизировать. Итоговое решение получается несколько иным, чем в разборах на платформе и на иных ресурсах, которые я видел. Надеюсь, данная статья поможет тем, кто, прочитав разборы задачи, всё равно не уверен, что до конца понял решение. А также тем, кто не уверен, что смог бы придумать данное решение на собеседовании.
Условие задачи Ссылка на заголовок
У нас есть n
столбиков: i
-й столбик находится на x-координате i
и имеет высоту h[i]
. Пусть мы выбрали два столбика на координатах (= с индексами) i
и j
, i < j
. Представим, что сверху между ними льют воду. Тогда столб воды поднимется максимум до уровня min(h[i], h[j])
: вся оставшаяся вода будет переливаться через более низкий столбик. Площадь налитой воды составит: ширина * высота = (j - i) * min(h[i], h[j])
.
В задаче необходимо найти максимальную площадь воды, помещающуюся между любой из возможных пар столбиков.
Ограничения: 2 ≤ n ≤ 10^5
, 0 ≤ h[i] ≤ 10^4
.
Небольшое отступление Ссылка на заголовок
Недавно ко мне обратились с вопросом по данной задаче. После чтения разбора задачи человеку считал, что он не конца понимает предложенное решение, а также ему было непонятно как можно было бы додуматься до этого решения на собеседовании. Я прочитал разбор задачи, и мне показалось, что правильность данного решения не так просто понять, несмотря на его лаконичную реализацию. Все разборы от пользователей LeetCode, которые я видел, и решения, описанные на других сайтах, были по сути перефразированием “официального” решения.
Для того чтобы объяснить, как можно решить эту задачу без “эврики” — внезапного осознания финального решения — я попробовал решить её несколько по-другому. В данной статье я описываю то, что у меня получилось.
Мы напишем перебор и будем последовательно его улучшать.
Официальное решение Ссылка на заголовок
В официальном решении предлагают использовать метод двух указателей l = 0
, а r = n - 1
. Пусть ответ будет храниться в — ans
, изначально ans = 0
. До тех пор, пока указатели не встретятся, делаем следующее:
- Пытаемся обновить ответ
ans = max(ans, (r - l) * min(heights[l], heights[r]))
. - Сдвигаем тот указатель, который указывает на более низкий столбик:
if heights[l] < heights[r] { l++ } else { r-- }
- Ответ на задачу находится в
ans
.
Я почитал другие разборы данной задачи, в том числе разборы пользователей на самом LeetCode, а также другие разборы в интернете, и пришел к выводу, что все используют абсолютно точно такой же метод решения данной задачи.
Я не нахожу удивительным, что после чтения данного разбора у людей могут остаться вопросы и отсутствовать ощущение того, что действительно понял данную задачу. Более того, у меня есть подозрения, что бо́льшая часть людей, решивших данную задачу именно таким способом до конца не понимают, почему данное решение правильно работает, в пользу чего свидетельствует мой краткий опрос.
Вопросы, которые можно задать себе для проверки того, что мы действительно поняли это решение: почему истинно, что при использовании данного алгоритма мы либо уже проходили наилучшую пару столбиков, либо ещё её пройдём? Другими словами, почему мы уверены, что для наилучшей пары L
и R
, будет ситуация, когда l == L
и r == R
? Почему мы не можем “случайно” пропустить один из столбиков ответа?
Действительно, если прочитать, что тема данной задачи — два указателя, то можно достаточно просто додуматься до решения следующим образом:
Эта задача на тему “два указателя”. Следовательно, ставим один указатель на первый столбик, а другой — на последний. Пробуем обновить ответ. Теперь нужно сдвинуть указатели. Какой из указателей сдвигать? Тот, который указывает на бо́льший столбик? Разумеется, нет. Значит, сдвигаем тот, который указывает на меньший столбик. Продолжаем, пока указатели не встретятся. Отправляем, все тесты пройдены. Задача решена.
Давайте же попробуем решить задачу последовательно, начиная с простого перебора и заканчивая правильным решением.
Итеративный подход Ссылка на заголовок
Представим, что мы не знаем, как поступиться к данной задаче. Значит, попробуем написать перебор.
ans := 0
for l := 0; l < n - 1; l++ {
for r := l + 1; r < n; r++ {
ans = max(ans, (r - l) * min(heights[l], heights[r]))
}
}
Сложность данного решения — O(n^2)
. Хмм… под ограничения условия это не подходит. На новые мысли не наводит. Попробуем перебрать немного по-другому. Давайте перебирать высоту воды h
, которая будет вмещаться между двумя “наилучшими” столбиками. Да, перебирать все возможные значения от 0
до (максимального допустимого по условию) 10^4=10000
. Теперь, для каждой из высот воды, нужно найти пару столбиков, которые смогут вместить воду такой высоты. В целях максимизации площади, нас интересуют два столбика, который находятся как можно дальше друг от друга. Для поиска столбиков, поставим указатель l
на самый левый столбик, с индексом 0
, а r
— на самый правый (с индексом n - 1
). Данные столбики расположены на самом большом возможном расстоянии друг от друга. Теперь пропустим все столбики слева и справа, которые не позволяют вместить воду высотой h
, то есть все столбики, которые ниже, чем h
. Получившаяся пара указателей l
и r
— это самые удалённые друг от друга столбики, которые вмещают воду высотой h
.
ans := 0
for h := 1; h <= 10000; h++ {
l, r := 0, n - 1
for ; l < r && heights[l] < h; l++ {}
for ; l < r && heights[r] < h; r-- {}
ans = max(ans, (r - l) * h)
}
Сложность такого решения — O(H*n)
, где H
— максимальное возможное значение высоты, по условию это 10^4
.
Далее можно сделать следующее наблюдение. Высота воды h
при переборе монотонно увеличивается. Следовательно, если столбы l
и r
могут содержать воду высотой h
, то столб высотой h + 1
сможет содержать только либо та же пара столбиков l
и r
, либо какая-то пара столбиков внутри отрезка [l; r]
. Мы пропустили столбики 0..l-1
и r+1..n-1
, т.к. они не могли вместить меньшую высоту воды, а значит для ещё большей высоты воды они нам точно не подходят. Данное наблюдение позволяет нам сделать следующую оптимизацию: не пересчитывать l
и r
с начальных значений 0
и n-1
каждый раз, а обновлять значения для каждой высоты h
:
ans := 0
l, r := 0, n - 1
for h := 1; h <= 10000; h++ {
for ; l < r && heights[l] < h; l++ {}
for ; l < r && heights[r] < h; r-- {}
ans = max(ans, (r - l) * h)
}
Данное решение имеет сложность O(H + n)
, где H
— максимальная возможная высота, которая по условию не больше 10^4
. Данное решение уже успешно проходит все тесты на LeetCode, хоть и не является оптимальным для данной задачи из-за слабых ограничений на высоту столбиков. Чуть далее в статье ещё обсудим этот момент, а сейчас же представим, что диапазон возможных высот — больше, например 0 ≤ h ≤ 10^12
. Теперь наше решение будет работать долго и не пройдёт по ограничению времени. Попробуем найти ещё оптимизации перебора.
Пусть на некоторой итерации перебора у нас есть некоторые l
и r
. Можно сделать следующее наблюдение: во всех итерациях перебора h
не произойдёт никаких изменений до тех пор, пока h
не станет равно min(h[l], h[r])
, после чего будет сдвинут указатель l
и/или r
. Получается, нам не нужно перебирать все значения h
и мы можем поступить более оптимально, перебирая h
“прыжками”, пропуская “неинтересные” значения:
ans := int64(0)
l, r := 0, len(height) - 1
h := 0
for l < r {
h = min(height[l], height[r])
ans = max(ans, int64(r - l) * int64(h))
for ; l < r && height[l] <= h; l++ {}
for ; l < r && height[r] <= h; r-- {}
}
int64
в оригинальной задаче не нужен: он был использован только для того, чтобы поддержать увеличенный до10^12
диапазон высот столбиков и не получить переполнение при перемножении.
На каждой итерции мы:
- выбираем высоту столба воды
h
, так, чтобы она была максимальной для пары столбиковl
,r
; - пробуем улучшить ответ;
- высоту
h
мы обработали, поэтому для перехода к большей высоте на следующей итерации, мы пропускаем все столбики с высотой меньше либо равнойh
.
Теперь мы не зависим от диапазона возможных высот, так как убрали H
из оценки. Сложность получившегося решения — O(n)
, что является наилучшей асимптотической сложностью решения данной задачи, ведь для решения данной задачи необходимо пройтись хотя бы по одному разу по каждому элементу входных данных.
Напомню пройденные этапы:
- написали перебор всех пар столбиков;
- подумали, как его можно улучшить. Не придумали;
- написали перебор по-другому, через перебор высоты столба воды в ответе;
- заметили свойство и использовали его для улучшения перебора;
- также заметили и использовали ещё одно свойство для улучшения асимптотики;
- получили наилучшую возможную асимптотическую сложность.
В некоторых задачах, к которым непонятно как подступиться, перебор и его последовательная оптимизация могут привести к правильному решению.
Сравнение решений Ссылка на заголовок
Давайте реализуем решение из разбора:
ans := 0
l, r := 0, n - 1
for l < r {
h = min(heights[l], heights[r])
ans = max(ans, (r - l) * h)
if heights[l] < heights[r] {
l++
} else {
r--
}
}
Нетрудно заметить схожесть нашего решения и решения из других разборов. Как и в нашем решении, столбик с меньшей высотой будет отброшен раньше столбика с большей высотой. Отличие заключается в том, что в нашем решении при помощи внутренних циклов мы отбрасываем больше пар, которые точно не обновят ответ, в то время как в этом больше возможных пар столбиков, даже если некоторые из них определённо не обновят ответ. Иными словами, здесь нет монотонно возрастающей последовательности возможных высот столба воды h
. Стоит заметить, что код сдвига указателей здесь возможно выглядит немного проще, однако проще ли понять правильность его работы? Я бы сказал, что нет.
Ни в одном разборе, который я видел, не было упоминаний об избыточности проверяемых пар столбиков и, что можно дополнительно вести монотонно возрастающую последовательность высот.
Что не так с LeetCode Ссылка на заголовок
Эта задача идёт под номером 11 из нескольких тысяч задач на платформе. Казалось бы раз она идёт в списке задач так рано, то она должна быть хорошо проверена, содержать хорошие ограничения и тесты. Однако, решение с перебором по всем высотам, которое не является наилучшим решением этой задачи, проходит все тесты. Решивший её таким перебором мог бы остановиться на данном способе, так и не решив задачу способом, который подразумевался авторами. Скорее всего, ограничение на высоту 10^4
потому, что оно не приводит к переполнению типа int
при перемножении максимальной высоты на максимальное расстояние между столбиками 10^5
. Однако, это не отменяет факт того, что ограничения и тесты могли бы быть в данной задаче более строгими.
Даже в рамках ограничений, предложенных в задачах, на платформе иногда встречаются проблемы со слабыми тестами. Проблема по всей видимости в том, что основной приоритет на платформе в размере архива задач, нежели в тщательности подготовки каждой из них.
Что же с этим делать? На LeetCode, да и в целом, даже после успешной отправки решения, неплохо задавать себе вопрос:
Можно ли решить данную задачу с лучшей асимптотической сложностью?