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