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

Конечно! Задача 42 на LeetCode называется "Trapping Rain Water". Мы попытаемся понять, как работает метод двух указателей для решения этой задачи.

### Суть задачи

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

### Пример

```
Высоты: [0,1,0,2,1,0,1,3,2,1,2,1]
```

На этом примере после дождя между стенами образуется определенное количество воды.

### Метод двух указателей

Теперь рассмотрим метод двух указателей, который позволяет эффективно решить эту задачу.

1. **Инициализация указателей**: 
   Мы создаем два указателя: один (left) начинается с начала массива, а другой (right) — с конца массива. Также нам нужно будет хранить максимальные высоты на текущих позициях этих указателей (max_left и max_right).

2. **Движение указателей**:
   - Если высота, на которую указывает левый указатель (heights[left]), меньше или равна высоте правого указателя (heights[right]), это означает, что мы можем "забрать" количество воды, равное разнице между max_left и высотой текущего левого указателя. После этого мы двигаем левый указатель вправо (left++).
   - Если высота правого указателя больше высоты левого, аналогично, мы можем "забрать" воду, и затем двигаем правый указатель влево (right--).

3. **Почему движем указатель с меньшей высотой?**:
   - Важно понимать, что вода может застояться только до уровня, закрытого самой высокой стеной с обеих сторон. Если мы находимся на меньшей высоте, это означает, что это "ограничение" на нашем пути к центральной части. Двигая указатель с меньшей высотой, мы можем потенциально найти "высокую стену" и увеличить максимальную высоту с той стороны.
   - Например, если мы находимся на позиции с высотой 1 и у нас есть стена высотой 2, то возможна застройка воды. Но если другая стена ниже, чем 1, мы не можем "забрать" воду, прежде чем найти более высокую стену.

### Итоговый алгоритм

- Инициализация переменной для хранения результата (количество воды).
- Запускаем цикл, который продолжается, пока left < right.
- Внутри цикла сравниваем высоты и обновляем максимальные значения и общее количество воды в зависимости от высоты и указателей.

Таким образом, мы уменьшаем время выполнения до O(n), потому что обходим массив только один раз. 

Если у вас есть какие-либо вопросы по этому алгоритму, пожалуйста, дайте знать!

Рассмотрите один столбик (допустим, номер i). Какой высоты в нем может быть вода? Обозначим за x. Она не должна выливаться ни слева ни справа. Значит, с  обеих сторон должен быть столбик с высотой хотя бы x. Раз есть хотя бы один, то максимум точно должен быть хотя бы x. Отсюда x <= max(h[0..i-1]) и x <= max(h[i+1..n-1]) Значит высота воды в i-ом столбике:  min(max(h[0..i-1]), max(h[i+1..n-1])). Уже можно просто вот это подсчитать за 2 прохода и получить решение. Ну, только не забыть что там надо max(x, h[i])-h[i] к ответу прибавить, ведь если текущий столбик слишком высокий, то вся вода с него стечет. 
 
 Но можно думать дальше. Давайте обрабатывать не все столбики подряд, а посмотрим с краев. С крайних столбиков все, понятно, вытекает наружу. Пусть крайний левый меньше. Рассмотрим второй столбик слева. Мы уже знаем max(h[0..i-1]) в нем - это один левый столбик. И оно точно меньше max(h[i+1..n-1]), потому что справа уже есть крайний столбик, который выше самого левого. Мы незнаем точное значение max(h[i+1..n-1]), но мы знаем что max(h[i+1..n-1]) >= h[n-1] >= h[0] = max(h[0..i-1]). Вот мы знаем высоту воды в столбике 1, мы же берем минимум из двух значений. Даже если мы не знаем максимум справа, мы знаем, что он точно больше максимума слева и в ответе не участвует. 
 
 Вот мы и обработали второй столбик. Теперь перейдем к третьему. При этом можно первые 2 столбика объеденить в один высоты max(h[0], h[1]). Это и есть сдвиг указателя, только при этом мы смотрим не на сам столбик, а аккумулируем максимумы с краев. 
 
 Но, если бы мы смотрели на второй справа столбик, рядом с большим их двух крайних, то мы не могли бы сразу сказать, а какая там высота воды. Мы в нем знаем max(h[i+1..n-1]) - высота последнего столбика. Но какое в нем max(h[0..i-1]) мы не знаем и не можем сказать, больше ли оно или нет, а значит, не можем посчитать x.