Сколько воды утекло? Решаем задачу лунной походкой на Haskell

5 будет. 3 над единицей и 2 над тройкой. В этой задаче считается, что слева и справа от исходных данных стоят нули.

func trap(height []int) int {
    result, left, right := 0, 0, len(height) - 1
    maxL, maxR := 0, 0
    for left < right {
        if height[left] < height[right] {
            if height[left] > maxL {
                maxL = height[left]
            } else {
                result += maxL - height[left]
            }
            left++
        } else {
            if height[right] > maxR {
                maxR = height[right]
            } else {
                result += maxR - height[right]
            }
            right--
        }
    }
    return result
}

Как всегда хабр в последнюю секунду не даёт редактировать. Вызов функции min лишний, у нас по построению и так понятно где что:

water :: [Int] -> Int
water xs = transformResult $ foldl' go ([], 0) xs where
  transformResult ([], result) = result
  transformResult ([_], result) = result
  transformResult (_:elm:xs, result) = result + getIntermediateResult elm xs

  go ([], result) elm = ([elm], result)
  go (x:xs, result) elm = if x > elm then (x:elm:xs, result) else ([elm], result + getIntermediateResult (min x elm) xs)

  getIntermediateResult roof elms = sum $ (\x -> roof - x) <$> elms

Соответственно вариант без промежуточного списка с одним только состоянием:

data WaterState = Empty | NonEmpty Int Int Int deriving Show

water :: [Int] -> Int
water xs = snd $ foldl' go (Empty, 0) xs where
  go :: (WaterState, Int) -> Int -> (WaterState, Int)
  go (Empty, result) elm = traceShowId (NonEmpty elm elm 1, result)
  go (NonEmpty x s count, result) elm = traceShowId $ if x > elm then (NonEmpty x (s + x - elm) (count + 1), result) else (NonEmpty elm elm 1, result + getResult x elm count s) where
    getResult x elm count s = (if x <= elm then s else s - (x - elm) * count) - x

Он не работает для стакана у которого последняя левая стенка выше правой, но в целом как мне кажется иллюстрирует идею. Тут уже гарантированно все элементы обходятся 1 раз, и промежуточных списков просто нет. Хотя по-хорошему такой код я бы писать, конечно, не рекомендовал)