Created
July 26, 2013 01:54
-
-
Save alaingilbert/6085432 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class HistogramProblem(object): | |
| def __init__(self, arr): | |
| self.arr = arr | |
| def water_in_range(self, left, right): | |
| count = 0 | |
| minimum = min(self.arr[left], self.arr[right]) | |
| for i in range(left+1, right+1): | |
| tmp = minimum - self.arr[i] | |
| if tmp > 0: | |
| count += tmp | |
| return count | |
| def solve(self): | |
| left = 0 | |
| right = len(self.arr) - 1 | |
| water_count = 0 | |
| ptr = left + 1 | |
| while ptr <= right: | |
| if self.arr[ptr] >= self.arr[left]: | |
| water_count += self.water_in_range(left, ptr) | |
| left = ptr | |
| ptr += 1 | |
| ptr = right - 1 | |
| while ptr >= left: | |
| if self.arr[ptr] >= self.arr[right]: | |
| water_count += self.water_in_range(ptr, right) | |
| right = ptr | |
| ptr -= 1 | |
| return water_count | |
| print HistogramProblem([1, 0, 3, 0, 2, 0, 1, 0, 3]).solve() # Should be 13 | |
| print HistogramProblem([0, 1, 2, 3, 0, 3, 1]).solve() # Should be 3 | |
| print HistogramProblem([1, 0, 2, 3, 4]).solve() # Should be 1 | |
| print HistogramProblem([4, 0, 2, 3, 4]).solve() # Should be 7 | |
| print HistogramProblem([3, 0, 0, 0, 3]).solve() # Should be 9 | |
| print HistogramProblem([3, -2, 0, 0, 3]).solve() # Should be 11 | |
| print HistogramProblem([3, 0, 4, 0, 3]).solve() # Should be 6 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment