leetcode 【 Container With Most Water 】python 实现

题目：

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

代码：oj测试通过 Runtime: 132 ms

 class Solution:

     # @return an integer

     def maxArea(self, height):

         # none case or one element case

         if height is None or len(height)<2:

             return 0

         # left point and right point

         left = 0

         right = len(height)-1

         max_container = 0

         while left<right :

             curr_container = min(height[left],height[right]) * (right-left)

             max_container = max(curr_container,max_container)

             if height[left]>height[right]:

                 right = right-1

             else:

                 left = left+1

         return max_container

思路：

数组前后双指针技巧。

有点儿像动态规划。

两个指针一左一右left right

面积为：min(height[left],height[right])*(right-left)

指针迭代条件为：哪边的指针所指位置的高度小，就从哪边往中间移动。每一步更新一次max_container的值。

为什么哪边的指针所指的位置高度小就从哪边往中间移动呢？能装多少水是有较短的那边决定的，因此如果寻求装更多的水，则应该优先从较短的一侧开始求变。

这样一来，每一次迭代后，都保证max_container保存了当前以及之前的可能最大蓄水量。

巴特西

leetcode 【 Container With Most Water 】python 实现

最新文章

热门文章