Наводнение

Дан массив целых положительных чисел, который представляет собой карту высот сложенного из кубиков 1x1 макета местности. Макет полностью погружают под воду, а затем поднимают. При этом часть воды остаётся в углублениях макета, а часть стекает влево или вправо.

Например, массив, местность и оставшаяся вода могли бы выглядеть так:

Напишите функцию, которая принимает на вход массив - карту местности и возвращает одно число - объём оставшейся воды. Желательно, чтобы алгоритм работал за линейное время (от длины массива).

Решение
Я напишу относительно простое решение, которое требует линейного времени и линейной же памяти.

Можно сделать следующее наблюдение: для того, чтобы посчитать уровень воды над i-м элементом, нужно знать максимальную высоту местности слева и справа от него, т.е. два числа L=max(h₀,...,h_i-1) и R=max(h_i+1,...,h_n). Зная эти два числа, мы можем вычислить, что над i-м элементом вода стоит на уровне min(L,R), а собственно высота столба воды равна max(0, min(L,R) - h_i).

Решением в лоб было бы вычислять L и R заново для каждого элемента, т.е. написать что-то такое:

public int volumeOfWater(int[] h) {
    int volumeOfWater = 0;
    for (int i=0; i<h.length; i++) {
        int L = max(h, 0, i);
        int R = max(h, i+1, h.length);
        int minBorderHeight = Math.min(L, R);
        volumeOfWater += Math.max(0, minBorderHeight - h[i]);
    }
    return volumeOfWater;
}

private int max(int[] h, int from, int to) {
    int max = 0;
    for (int i=from; i<to; i++) {
        if (h[i] > max) {
            max = h[i];
        }
    }
    return max;
}

Такой подход дал бы квадратичную сложность: для каждого из N элементов потребовалось бы просмотреть N-1 элементов, чтобы вычислить L и R.

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

Полный код выглядит так:

public int volumeOfWater(int[] h) {
    int[] R = calculateR(h);    
    int volumeOfWater = 0;
    int L = 0;
    for (int i=0; i<h.length; i++) {
        volumeOfWater += Math.max(0, Math.min(L, R[i])-h[i]);
        if (h[i] > L) {
            L = h[i];
        }
    }
    return volumeOfWater;
}

private int[] calculateR(int[] h) {
    int[] R = new int[h.length];
    if (R.length == 0) {
        return R;
    }

    R[R.length-1] = 0;
    for (int i=h.length-2; i>=0; i--) {
        R[i] = Math.max(R[i+1], h[i+1]);
    }
    return R;
}

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

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

public int volumeOfWater(int[] h) {
    int volumeOfWater = 0;
    int globalMaxIndex = maxIndex(h);
        
    int leftMax = 0;
    for (int i=0; i<globalMaxIndex; i++) {
        if (h[i] > leftMax)  {
            leftMax = h[i];
        }
        volumeOfWater += (leftMax - h[i]);
    }
        
    int rightMax = 0;
    for (int i=h.length-1; i>globalMaxIndex; i--) {
        if (h[i] > rightMax) {
            rightMax = h[i];
        }
        volumeOfWater += (rightMax - h[i]);
    }
        
    return volumeOfWater;
}
    
private int maxIndex(int[] h) {
    int max = 0;
    int index = 0;
    for (int i=0; i<h.length; i++) {
        if (h[i] > max) {
            max = h[i];
            index = i;
        }
    }
    return index;
}