【LeetCode 11】Container With Most Water (Python)

Question:

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 and n is at least 2.

Solution:

无非是从大到小依次寻求最大解的问题，每一次都有一对变量，而结果是以较小的值为准，当然变换较小的变量，尝试寻求最大解，不过在比较大小时，由于有x,y，所以变换也有两种方式：固定一方有序从大到小，寻找另一方变换带来较大值的可能性

1 固定x有序，变换y寻求可能性：对两个变量而言，以x为准从大到小，即由最两端开始，逐渐往中间寻找较大的y值替换原有两个变量中较小的y值带来的可能性

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        area=0
        l,h=0,len(height)-1
        while l<h:
            area=max(area,(h-l)*min(height[l],height[h]))
            mi=min(height[l],height[h])
            while height[l]<=mi and l<h:l+=1
            while height[h]<=mi and l<h:h-=1
        return area
        

2 固定y有序，变换x寻求可能性：以y为准（即高度），需要先把y排序，再从大到小遍历，观察x轴上较大的距离替换 带来的可能性

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        indexes=[i for i in range(len(height))]
        cors=zip(indexes,height)
        cors=sorted(cors,key=lambda x:x[1],reverse=True)
        a,b=cors[0],cors[1]
        area=abs(a[0]-b[0])*min(a[1],b[1])
        for c in cors[2:]:
            b_area=abs(c[0]-b[0])*c[1]
            a_area=abs(c[0]-a[0])*c[1]
            if max(abs(c[0]-a[0]),abs(c[0]-b[0]))>abs(a[0]-b[0]):
                if a_area>b_area:
                    if a_area>=area:
                        area=a_area
                    b=c
                elif b_area>a_area:
                    if b_area>=area:
                        area=b_area
                    a=c
        return area
        

Attention:

在依照一个维度从大到小遍历时，对另一维度的记录不应该以最终结果area为准，有时候另一维度上的值变大了，但是最终结果依然较小，如果此时不变换该维度上记录的较小值，就失去了继续在该维度上寻找更多较大值的机会，可能会错过最优解。