[LeetCode]题解（python）：011-Container With Most Water

时间：2021-11-30 00:09:45

题目来源：

https://leetcode.com/problems/container-with-most-water/

题意分析：

给出一个n长度的非0数组，a1,a2,……,an，ai代表在坐标i上的高度为ai。以以ai，aj为高，i到j为底，可以构造出一个容器。那么求出这些容器中可以装的水的最大容积（容器不能倾斜）。例如数组[2,1]，一共可以构造1个容器，这个容器的四个端点坐标是（0，0），（0，2），（1，1），（1，1），那么他可以装的最大的水容积是（1-0）*1 = 1.

题目思路：

     我们不难发现，水容积的大小是由短高度决定的。暴力的方法就是把所有的容器找出来，算出他们的水容积，一一比较，然后得到最大值，这种方法的时间复杂度是（O（n^2））。很明显会TLE。

我们认真研究一下寻找过程，我们从第一个高度为起始容器壁，那么我们直接以最后一个高度为终止壁，如果a1 <= an，那么以a1为起始的容器最大是a1 * （n - 1），以a1为容器壁的最大容器计算出来的。那么以a1为壁的所有情况不需要再考虑，接着考虑a2的；同理，如果a1 > an,an不再考虑，考虑an-1，这有点类似"夹逼定理"。比较ai和aj（i<j）如果ai <= aj，i++；否者j ++直到i == j。这个算法的时间复杂度是（O（n））。

代码（python）：

 class Solution(object):

     def maxArea(self, height):

         """

         :type height: List[int]

         :rtype: int

         """

         size = len(height) # the size of height

         maxm = 0 # record the most water

         j = 0

         k = size - 1

         while j < k:

             if height[j] <= height[k]:

                 maxm = max(maxm,height[j] * (k - j))

                 j += 1

             else:

                 maxm = max(maxm,height[k] * (k - j))

                 k -= 1

         return maxm

转载请注明出处：http://www.cnblogs.com/chruny/p/4817787.html

相关文章