Несколько лет назад я пошел с другом в парк развлечений, и он предложил мне прокатиться с ним на аттракционе под названием Ripcord. Если вы не знаете, что это за поездка, они привязывают вас к упряжи, тащат вас между тремя башнями лесов, а затем бросают. Это казалось таким выполнимым, пока я не стоял у основания этих башен в упряжи и смотрел прямо вверх. И, честно говоря, именно так возникают некоторые вопросы по литкоду. Название говорит Контейнер с наибольшим количеством воды, и вы думаете: Вау, звучит так выполнимо. Затем вы открываете его, и он кажется таким пугающим. Но в тот день меня подбросило в воздух на 180 футов и я упал. Каким бы ужасным это ни было до того, как я это сделал, после я понял, что это было не так пугающе, как казалось. Это верно и для этого вопроса о литкоде, и я здесь, чтобы помочь вам разобраться с ним.

Первая проблема для меня в любом вопросе о литкоде — понять реальную проблему, и именно отсюда поначалу исходит много запугивания. Итак, давайте взглянем на инструкцию к задаче с литкодом Контейнер с наибольшим количеством воды. Мы будем решать эту задачу на Javascript просто для ознакомления.

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.

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

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

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

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

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

  1. Это двухмерная сетка, нас не волнует глубина пространства
  2. Мы не можем просто выбрать две самые высокие полосы, потому что расстояние между полосами будет влиять на то, сколько воды можно удержать.
  3. Точно так же мы не можем выбрать два самых дальних столбца, потому что высота столбцов будет влиять на то, сколько воды можно удерживать.
  4. Реальный ключевой важный факт здесь. Маловероятно, что мы найдем две полосы одинаковой высоты, и в этом случае меньшая полоса высоты будет определять количество удерживаемой воды.

Помните об этом, пока мы идем вперед. Когда я впервые подошел к этому, это, честно говоря, было немного ошеломляющим. Мне нужно было так много сделать и учесть, различные высоты, как найти наибольшую площадь, как выполнить расчет, и, кроме того, я хотел получить это время O (n)! Мой мозг закружился.

Сначала мы собираемся искать решение грубой силы. И мы собираемся разбить это на шаги. Первое, что я сделал, это выяснил, как вычислить площадь. Поэтому я буквально вытащил блокнот и просто написал несколько заметок. Я придумал вот что.

  1. Мне нужно было определить, какая стена (число в массиве) больше
  2. Мне нужно было вычислить расстояние между стенами, вычитая их индексы
  3. Мне нужно было умножить значение меньшей стены на разницу индексов

В этот момент все просто щелкнуло. Я знал, как получить площадь двух стен, поэтому теперь все, что мне нужно было сделать, это сравнить их, чтобы получить решение грубой силы. Поэтому я установил переменную, содержащую наибольшее количество воды, создал двойной цикл, затем использовал функцию Math.max в Javascript, чтобы пройти через каждую возможную область и всегда сохранять самую высокую. Вот как это выглядит, и если вы этого не понимаете, не волнуйтесь, я все равно пройдусь по ним строчка за строчкой. Следует отметить, что я изменил имя аргумента с height на heights, потому что это имело для меня больше смысла. так как он принимал несколько значений.

var maxArea = function(heights) {
    let highestWater = 0
    for (let i = 0; i < heights.length; i++) {
        for (let j = (i + 1); j < heights.length; j++) {
            const smallerWater = Math.min(heights[i], heights[j])
            const currentWater = (smallerWater * (j-i))
            highestWater = Math.max(currentWater, highestWater)
        }
    }
    return highestWater
}

Построчно для решения грубой силы:

let highestWater = 0

Это довольно легко. Это переменная, которую я установил, чтобы удерживать самую высокую воду. Поскольку все значения неотрицательны, я чувствовал себя в безопасности, начав его с нуля.

Давайте поговорим о том, что делает этот двойной цикл!

for (let i = 0; i < heights.length; i++) {
        for (let j = (i + 1); j < heights.length; j++) {
  }
}

Если вы знакомы с двойными циклами в javascript, вы можете пропустить это ;) Но если вы не совсем понимаете, я проведу вас через это.

Первый цикл будет выполняться, пока i меньше, чем heights.length, и он начинается с 0. Итак, если в массиве heights 5 чисел, цикл будет выполняться 4 раза, потому что, когда он достигает 5, он теперь будет равен к высотам. Итак, если бы наш входной массив был [1,8,6,2] и мы сделали «console.log(heights[i])», он записал бы 1, 8, 6, 2.

Второй цикл аналогичен тому, что он также остановится, когда достигнет конца длины массива, НО есть важное отличие. Я инициирую переменную j как i + 1. Разница, которая будет иметь значение, заключается в следующем. Допустим, мы должны были записывать в консоль эти значения, снова ожидая ввода [1,8,6,2].

for (let i = 0; i < heights.length; i++) {
    console.log(heights[i])
        for (let j = (i + 1); j < heights.length; j++) {
        console.log(heights[j])
  }
}

Наша консоль будет выглядеть так. 1, 8, 6, 2, 8, 6, 2, 6, 2, 2. Имеет ли это смысл? Если нет, то вот еще один визуал. Я собираюсь написать это снова с (i) или (j) в зависимости от того, какой цикл регистрирует число. 1(i), 8(j), 6(j), 2(j), 8(i), 6(j), 2(j), 6(i), 2(j), 2(i). По сути, я работаю с двумя точками, i и j.

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

const smallerWater = Math.min(heights[i], heights[j])

В этой строке кода я использую Math.min(), которая принимает два аргумента (или вы можете использовать оператор распространения для расширения массива в качестве аргумента) и возвращает наименьшее значение. В этой вазе я использую его для присвоения меньшего индекса между моим указателем i и моим указателем j. Так что это буквально выбор меньшей стены/бара. Например, если бы мой ввод был [1,8,6,2], и я был бы по индексу 1, а j был по индексу 3, меньшая вода была бы = к 2.

const currentWater = (smallerWater * (j-i))

Затем я вычисляю площадь воды между барами, на которых в данный момент находятся мои точки, умножая значение меньшего бара на разницу индексов. Помните, что j начинается с i+1, поэтому j ВСЕГДА будет больше i, поэтому можно безопасно вычесть j из i, чтобы получить расстояние. Следуя примеру из последнего абзаца, если j = 3, i=1 и smallWater = 2, наша математика выглядит так. (2 * (3–1)). 3–1 находится в скобках, поэтому мы сначала вычитаем это и получаем 2, и теперь у нас есть (2 * 2), а 2 * 2 = 4. Таким образом, currentWater будет = 4.

highestWater = Math.max(currentWater, highestWater)

Последнее, что я сделал, это присвоил той переменной, которую мы установили вне двойного цикла, высшей воде значение = = для Math.max(currentWater, highWater). Помните Math.min? Что ж, Math.max буквально делает прямо противоположное. Он возвращает более высокое значение. Таким образом, он сравнивает currentWater с тем, что было сохранено ранее в highWater, сохраняет то, что выше, и продолжает свой зацикленный путь.

Теперь, если вы введете это решение в leetcode, оно примет его, если вы нажмете runcode. Но он не примет его, если вы нажмете «Отправить».

Это потому, что это вопрос уровня СРЕДНЕГО, и они ожидают лучшей оптимизации, чем решение методом грубой силы. Это означает, что один из тестов отправки имеет ОГРОМНЫЙ массив, который истечет время ожидания вашего кода. Он действительно не хочет делать какие-либо махинации с двойной петлей. Итак, теперь, когда мы нашли решение грубой силы. Пришло время оптимизировать.

Есть несколько вещей, которые следует учитывать, когда мы рассматриваем оптимизацию. Прежде всего

  1. Только меньшая полоса имела значение для нашей математики, помните, что мы выбирали между большей и меньшей полосой.
  2. На самом деле мы ничего не делаем во внешнем цикле. Это был просто удобный способ сверить каждый элемент с самим собой.

При этом я знал, что решением будет метод с двумя указателями. Но поначалу мне было немного трудно реализовать это, потому что я впервые применил это на практике. Итак, давайте поговорим об этом. Что такое 2-указательный метод?

На самом деле, это просто использование двух указателей в одном цикле и перемещение их по массиву. Хотя чаще всего вы будете видеть это. Один указатель слева, один указатель справа, и они встречаются где-то посередине. Часто это отличный способ выйти из вложенного цикла. Теперь имейте в виду, что когда мы сравниваем эти указатели, имеет значение только меньшее значение, что облегчает решение, что перемещать.

Итак, давайте посмотрим и рассмотрим оптимизированное решение построчно.

var maxArea = function(heights) {
    if (heights.length <= 1) return 0
    let highestWater = 0;
    
    let p1 = 0
    let p2 = heights.length-1
    
    while (p1 < p2) {
        const smallerWater = Math.min(heights[p1], heights[p2]);
        const width = p2 - p1;
        const currentWater = smallerWater * width;
        highestWater = Math.max(highestWater, currentWater);
        heights[p1] <= heights[p2] ? p1++ : p2-- 
        
    }
    return highestWater
}

Итак, сначала мы начнем с

if (heights.length <= 1) return 0

Если длина массива высот меньше или равна 1, то умножать не на что, поэтому можно смело возвращать 0.

let highestWater = 0;
    
let p1 = 0
let p2 = heights.length-1

Далее мы устанавливаем некоторые начальные переменные. Как и раньше, highWater = 0. Затем я задаю переменные для своих указателей, вы можете назвать их левым и правым, i и j или p1 и p2. Все, что имеет для вас наибольший смысл. Левый указатель будет начинаться с 0, а правый указатель будет начинаться с длины массива минус 1, потому что помните, что массивы начинаются с 0, поэтому, если в массиве 5 элементов, эти индексы равны 0, 1, 2, 3. , 4, что означает, что нам нужно, чтобы наш второй указатель начинался с heights.length-1 (или, в моем примере, с индекса 4).

while (p1 < p2) {
}

Это довольно просто. Пока цикл. Пока указатель 1 меньше указателя 2. Если они ударят друг друга, он остановится.

const smallerWater = Math.min(heights[p1], heights[p2]);

Этот фрагмент кода выглядит знакомым? Должно. Это практически то же самое, что и в прошлый раз, за ​​исключением того, что на этот раз для вызова индексов используются переменные p1 и p2.

const width = p2 - p1;
const currentWater = smallerWater * width;

Это почти то же самое, но для удобства чтения я сохранил ширину в собственной переменной. Но текущая вода все равно = меньшей воде * (p2-p1). Так что ничего не изменилось.

highestWater = Math.max(highestWater, currentWater);

Точно так же. Это сводит тебя с ума? Вот единственная разница.

heights[p1] <= heights[p2] ? p1++ : p2--

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

Помните, в прошлый раз мы использовали это в качестве примера: [1,8,6,2]

P1 начинается с 1 (индекс 0) | P2 начинается с 2 (индекс 3)

Он рассчитает максимальную площадь. Ширина равна 4, а меньший столбец равен 1. 1*3 равно 3. Это становится нашей текущей водой. Наша самая высокая вода в настоящее время равна 0, поэтому, когда она вычисляет максимальное значение, 3 становится нашей самой высокой водой.

Затем он проверяет, 1 ≤= 2 ? 1 на самом деле меньше 2. Таким образом, указатель увеличивается на 1.

Теперь P1 находится на 8 (индекс 1)| P2 все еще на 2 (индекс 3)

Их ширина равна 2 (3–1), мы берем меньшее число (2) и умножаем его на ширину (2), и у нас есть 4, что становится текущей Водой. Текущая вода больше, чем самая высокая вода, поэтому самая высокая вода также становится равной 4.

8 ≤= 2? неа. Это означает, что мы уменьшаем указатель, который был на 2.

Итак, теперь наши указатели P1 находятся на 8 (индекс 1) | P2 находится на 6 (индекс 2)

Ширина 2–1 (1). Мы берем меньшее число (8 против 6, поэтому нам нужно 6) и умножаем его на ширину (1). 6x1 равно 6, что становится текущим значением Water. 6 больше, чем 4, поэтому она также становится самой высокой водой.

Поскольку наши указатели в настоящее время находятся на 1 и 2, следующее перемещение указателя сделает их равными и вырвет нас из нашего цикла.

И это самая легкая и приятная часть. На данный момент все, что нам нужно сделать, это вернуть наш ответ

return highestWater

И получайте удовольствие от осознания того, что:

Runtime: 76 ms, faster than 98.21% of JavaScript online submissions for Container With Most Water.
Memory Usage: 48.3 MB, less than 28.61% of JavaScript online submissions for Container With Most Water.

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

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