История изменений

Сначала идём по массиву слева направо, вода не может быть выше, чем высота самого высокого на текущий момент из пройденных здания. Текущая высота самого высокого здания у меня в current height, текущий объём воды в current water (что-то мне с утра сейчас кажется, что можно было обойтись без current water, сразу прибавлять к result, но не суть). Доходим до более высокого здания — сбрасывает current water в result, меняем current height.

Таким образом узнаем число воды слева вплоть до самого высокого здания (и номер самого высокого здания в массиве). Идём по массиву справа налево до этого здания, чтобы узнать сколько справа от него воды по такому же принципу.

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

EDIT: А не, current water нужен чтобы в случаях вроде 11211 отбросить накопившиеся 2 куба воды с правого краю при первом обходе.

Сначала идём по массиву слева направо, вода не может быть выше, чем высота самого высокого на текущий момент из пройденных здания. Текущая высота самого высокого здания у меня в current height, текущий объём воды в current water (что-то мне с утра сейчас кажется, что можно было обойтись без current water, сразу прибавлять к result, но не суть). Доходим до более высокого здания — сбрасывает current water в result, меняем current height.

Таким образом узнаем число воды слева вплоть до самого высокого здания (и номер самого высокого здания в массиве). Идём по массиву справа налево до этого здания, чтобы узнать сколько справа от него воды по такому же принципу.

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

EDIT: А не, current water нужен чтобы в случаях вроде 11211 отбросить накопившиеся 2 куба воды с краю при первом обходе.

Сначала идём по массиву слева направо, вода не может быть выше, чем высота самого высокого на текущий момент из пройденных здания. Текущая высота самого высокого здания у меня в current height, текущий объём воды в current water (что-то мне с утра сейчас кажется, что можно было обойтись без current water, сразу прибавлять к result, но не суть). Доходим до более высокого здания — сбрасывает current water в result, меняем current height.

Таким образом узнаем число воды слева вплоть до самого высокого здания (и номер самого высокого здания в массиве). Идём по массиву справа налево до этого здания, чтобы узнать сколько справа от него воды по такому же принципу.

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