water volume in histogram graph

//examples
// x marks the troughs' boundaries


       x
  x   ##
 ##   ##
 ##   ##
 ##   ##
x##  ### x
###  ### # x
########_###


          x
  x      ##
 ##     ###
 ##     ###
 ##     ###
x##  #  ### x
###  #  ### # x
###########_###


      x
    x #
  x # #
x # # #
#_#_#_#


x      
#     x
#     #
#   # #
#_#_#_#


x      
# x    
# # x  
# # # x
#_#_#_#

Find the boundaries of troughs. Trough has a decreasing slope followed by an increasing slope. For increasing slope, stop when the increasing slope ends or till value is greater than value at start while recording the highest so far (ex: W trough).

// time: O(n) typically but O(n^2) for last example, space: O(1)
(a):
    volume = 0
    i = 0
    while true:
        if i+1 == a.length:
            break
        // trough boundaries
        start = i
        // decreasing slope
        while i+1 < a.length && a[i] >= a[i+1]:
            i++
        end = i
        // increasing slope
        while i+1 < a.length && (a[i] <= a[i+1] || a[end] <= a[start]):
            i++
            if a[i] >= a[end]:
                end = i
        // trough volume
        level = min(a[start], a[end])
        for j = start, j <= end, j++:
            if a[j] < level:
                volume += level - a[j]
        i = end
    return volume

Get the max before and after for every i. Water level is min of the two maxs and volume is less a[i] of that.

// time: O(n), space: O(n)
(a):
    // max for i before itself
    maxbefore = new [a.length]
    max = 0
    for i = 0, i < a.length, i++:
        max = max(max, a[i])
        maxbefore[i] = max
    // max for i after itself
    maxafter = new [a.length]
    max = 0
    for i = a.length-1, i >= 0, i--:
        max = max(max, a[i])
        maxafter[i] = max
    // volume
    volume = 0
    for i = 0, i < a.length, i++:
        level = min(maxbefore[i], maxafter[i])
        volume += level - a[i]
    return volume

For histograms with gap between two bars, the volume between two bars is min of water levels at them.

//example


    # #
#   # #
#   # #
#   # #
# # # # 
# # # #   # 
#_#_#_#_#_#_#

// time: O(n), space: O(n)
(a):
    // max for i before itself
    maxbefore = new [a.length]
    max = 0
    for i = 0, i < a.length, i++:
        max = max(max, a[i])
        maxbefore[i] = max
    // max for i after itself
    maxafter = new [a.length]
    max = 0
    for i = a.length-1, i >= 0, i--:
        max = max(max, a[i])
        maxafter[i] = max
    // volume
    levelprev = 0
    for i = 0, i < a.length, i++:
        level = min(maxbefore[i], maxafter[i])
        volume += level - a[i]
        levelbetween = min(level, levelprev)
        volume += levelbetween
        levelprev = level
    return volume

[Hat tip to N]