Solution: We can still use DP to solve this problem in O(n). Basically, there are two factors decides the volume of the container: 1) the minimum of the two sides 2) how wide the container is. If the highest bars are just at the left and right end of the histogram, we know that by picking these two bars we can have the largest container. If the bars at the left and right end are not the two highest, we need to explore further to look at other combinations. Based on these observations, what we need is actually an increasing sequence from left to right and also an increasing sequence from left to right. The details of the algorithm is as follow:
- First model the histogram as an array h[i]. For example, h[] = {3, 1, 4, 7, 5, 2, 6}.
- Then find the two increasing sequences. The one from left to right is left[] = {3, 4, 7} and the one from right to left is right[] = {6, 7}.
- begin with the first elements in left[] and right[], calculate the volume of the container formed by these two bars, use max_v to store this volume (which is 3*5=15).
- Then select the smaller one of the two bars, make one advancement in the array which the smaller bar is from. For our example, between left[0] and right[0], left[0] is the smaller one. Therefore we advance to left[1], which is "4". Then we calculate the volume of the container formed by left[1] and right[0]. The volume is 4*3=12, which is smaller than the previous value 15, so we just keep the old value.
- Then we repeat the previous step, just advance the array which the smaller bar is from. We will get left[2] and right[0]. The corresponding volume is 6*2 = 12, which is still smaller than 15.
- Then we need to advance in right[], we will find right[1] and left[2] refer to the same bar. Since at this time, both left[] and right[] have been exhausted, our algorithm just abort.
- One more thing, when two bars left[i] == right[j], we need to advance both arrays and inspect left[i+1] and right[j+1] next.
Do we really need to find two increasing sequences?
ReplyDeleteLet's fix the left side of our container (the l-th bar). We need to scan the histogram from right to the position where H [r]< H [l]< H[r+1] (update the maxv during our scan).
If H [l+ 1]<= H [l]; ignore l+1 and continue with considering l+2 as the candidate for left.
Otherwise (i.e, H [l+1]> H [l]): continue from the last "r" and find the first position where H [r']< H [l+1]< H[r'+1]
...
Hi Amir,
ReplyDeleteI am not sure I understand your method correctly. I have two concerns here: 1) does "H [r]< H [l]< H[r+1]" always hold? 2) is your algorithm O(n)? it seems for each "the l-th bar", you need to do some scans.