Наводнение (продолжение)

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

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

На этом рисунке уровень слева сейчас ниже, поэтому мы будем делать шаг с левой стороны. Это даст нам возможность вычислить объём воды в лежащей перед нами яме: мы знаем, что слева яма ограничена водоразделом высоты 3, а справа в любом случае есть водораздел большей высоты (в предельном случае это может быть тот элемент, на котором стоит правый указатель).

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

public int volumeOfWater(int[] h) {
    if (h.length == 0) {
        return 0;
    }
        
    int v = 0;
    int L = -1;
    int R = h.length;
    int lmax = 0;
    int rmax = 0;
        
    while (L < R) {
        if (lmax < rmax) {
            L++;
            if (h[L] <= lmax) {
                v += lmax - h[L];
            } else {
                lmax = h[L];
            }
        } else {
            R--;
            if (h[R] <= rmax) {
                v += rmax - h[R];
            } else {
                rmax = h[R];
            }
        }
    }
        
    return v;
}