leetcode_11

发表于   |   分类于

Container With Most Water

题目戳这

题意

给一系列的点a1,a2,a3....an，作它们的关于x轴的垂直线，这样就形成了n条线段，问任选两条线段，求它们与x轴三条线段形成的”容器”最多能容纳多少体积的水。

解法

我们很容易想到，这个就是求最大的体积，而在不“封顶”的情况下，这个容器的长度是由较短的竖直边长度决定的。我们首先看比较容易解决的宽度。因为宽度是分布在x轴上的一系列的点之间的距离，那么我们发现，假设首先取头和尾的两条，长度为a1和an，那么

  • 当a1<an时，长度由a1决定，此时a1能形成的最大容器就是与an进行搭配，体积为(an-a2)*a1
  • 当a1>an是，长度由an决定，此时an能形成的最大容器就是与a1进行搭配，体积为(an-a1)*an

从上面的分析我们可以看出，当某个是短板的时候，那么它肯定与当前高的那个搭配是最好的，所以这时候我们就可以跳过短板，让高的那个与它的下一个进行搭配。

所以总的来说，算法就是这样的，我们首先取a1和an，然后用两个指针i=1,j=n,则比较a1和an的大小，如果a1小，那么此时它与an搭配肯定是最大的了，无需再与其他的高度计算，所以直接跳过a1,即i+=1，反之则j-=1，一直移动到i,j相等为止。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        i = 0
        j = len(height)-1
        mmax = -1
        while i<=j:
            w = j - i
            h = height[i] if height[i]<height[j] else height[j]
            mmax = mmax if mmax > w*h else w*h
            if height[i] > height[j]:
                j -= 1
            else:
                i += 1
            
        return mmax