Art

                     +--+            
                     |  |            
         +--+        |  +--+  +--+   
         |  |WW WW WW|  |  |WW|  |   
   +--+  |  +--+  +--+  |  +--+  +--+
   |  |WW|  |  |WW|  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+

  0  1  2  3  4  5  6  7  8  9  A  B   [INDEX]

Loop invariant with Stack/Queue

Sometimes, there may be an inconclusive result after a loop. you have to wait for one or more loop to merge them all to the final result.

loop

  if can merge
    merge and commit all pending data to result

  else
    save and wait

In this case, when a new bar comes, if it is greater than or equals to all saved bars, those bars can make up a container. The most important thing is that how much water the container can trap has nothing to do with later bars.

How much water, Bars and stones.

            +--+
            |  |
+--+        |  |
|  |WW WW WW|  |
|  +--+  +--+  |
|  |  |WW|  |  |
+--+--+--+--+--+

  3  4  5  6  7   [INDEX]

figure above show two bars with heights 2 and 3. so the container can trap MIN(2,3) * (7 - 3 - 1) = 6.

but, wait, there are 2 stones (Bar 4 and Bar 6) in the water, we should take them away. 6 - 2 = 4.

// input bars are guaranteed that 
//     * there are more than 2 bars 
//     * first and last bar are the highest

function containWater(bars)

   left  = bars.first
   right = bars.last

   // container
   water = MIN(left.height, right.height) * (right.pos - left.pos - 1)

   // remove stone

   foreach bar in bars without first and last
     water = water - bar.height


   return water

Animation

  • Bar 0 height 0
  • Water = 0
Storage: 






+--+
  0  [INDEX]
  • Bar 1 height 1
  • containWater(Bar 0 .. Bar 1) = 0
  • Remove bars(Bar 0) no longer needed
  • Water = Water + 0
  • Save Bar 1
Storage:



+--+
|  |
+--+
  1  [INDEX]
  • Bar 2 height 0
  • Not meet the requirement to call containWater (new bar's height 0 < saved bar's height 1)

  • Bar 3 height 2

  • It is time to call containWater

  • containWater(Bar 1 .. Bar 3) = 1

  • Water = Water + 1

      +--+
      |  |
+--+  |  |
|  |WW|  |
+--+--+--+
  1  2  3   [INDEX]
  • Save Bar 3
Storage:


+--+
|  |
|  |
|  |
+--+
  3   [INDEX]
  • Deal with Bar 3, 4 , 5 , 6
  • Not meet the requirement to call containWater
  • Save them
Storage:

            +--+
            |  |
+--+        |  |
|  |WW WW WW|  |
|  +--+  +--+  |
|  |  |WW|  |  |
+--+--+--+--+--+

  3  4  5  6  7   [INDEX]
  • Bar 7 is the higher than any saved Bar, so call containWater
  • containWater(Bar 3 .. Bar 7) = 4
  • Water = Water + 4

Bars left in Storage

After the loop ends, there left some bars in the storage. From the figure below, there is 1 water in left bars. but, no bar can trigger code to call containWater.

Storage:

+--+            
|  |            
|  +--+  +--+   
|  |  |WW|  |   
|  |  +--+  +--+
|  |  |  |  |  |
+--+--+--+--+--+

  7  8  9  A  B   [INDEX]

How much water these bar can trap has nothing to do with any other bars, so we can convert the storage to a familiar question.

Yes, just reverse it to a new one.

            +--+
            |  |
   +--+  +--+  |  
   |  |WW|  |  |  
+--+  +--+  |  |  
|  |  |  |  |  |  
+--+--+--+--+--+

  0  1  2  3  4   [INDEX]

Now, add trap( new one ) to water