Почему это работает
- Вода над столбиком поднимается до меньшей из двух стенок: самого высокого столбика слева от него и самого высокого справа. Выше — перельётся через меньшую.
- Если leftMax ≤ rightMax, справа уже есть стенка не ниже leftMax, а настоящий максимум справа может быть только выше. Значит, над left вода — ровно leftMax минус его высота, что бы ни стояло между указателями. Справа — так же, зеркально.
- Поэтому двигаем сторону с меньшим максимумом: воду над её столбиком мы уже знаем точно, и каждый шаг закрывает один столбик навсегда.
Сложность
Время O(n): каждый шаг закрывает один столбик и сдвигает один указатель, всего n шагов. Память O(1): два указателя, два максимума и сумма, без массивов максимумов для каждого столбика.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗