Question: http://oj.leetcode.com/problems/container-with-most-water/
Question Name: Container With Most Water
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Solution: # @return an integer def maxArea(self, height): area = 0 left, right = 0, len(height)-1 # Without loss of generality, we consider the left is lower than right. # Our goal is to find out the container with most water. Equally, we # are finding out the slice, whose borders form a container with most # water. So a brute force method is: examine all the slices between # current left and current right. # # And all the slices between left and right = ( all the slices # between left+1 and right) + (all the slices beginning with left). # # Among all the slices beginning with left, the current [left, right] has # the maximum water: height_of_left * (right - left). For any other slice, # begin with left, the width (right - left) would be less. And the height # would be equal or less. # # As a result, for all the slices beginning with left, we just need to # consider the current one [left, right]. while left < right: area = max(area, (right-left)*min(height[left], height[right])) if height[left] < height[right]: left += 1 else: right -= 1 return area |