**Problem:**Pour water on a histogram, calculate the water volume the histogram can hold.

Solution: This is a relatively simple DP problem. Here we only give the main idea.

- For a particular bar
*bi*, if we know the highest bar on its left*Li*and highest bar on its right*Ri.*If the height of*bi*is smaller than both*Li*and*Ri*, the water volume can be held on this bar is min(*Li, Ri*) -*hi*; otherwise, it can't hold water. - To calculate
*Li*and*Ri*, we just need to record the maximum height we had observed so far from the left (and from the right). Therefore, a O(n) algorithm is straightforward here.

This comment has been removed by the author.

ReplyDeleteI should say your algorithm is not clear. :)

ReplyDeleteHow do you keep track of largest number on both left and right side?

ReplyDeleteThis algorithm requires O(n) space, but there is an algorithm that requires only O(1) space

ReplyDelete