Рассмотрите один столбик (допустим, номер 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.
Простой
