Login light

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

错误示范 此答案超出时间限制

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxArea = 0
        for i in range(len(height)-1):
            for o in range(i+1,len(height)):
                lang = o - i
                wide = min(height[i], height[o])
                if lang * wide > maxArea:
                    maxArea = lang * wide
        return maxArea

思路:
O(n^2)的方法会超出时间限制,即使简化算法也一定要遍历一遍,所以要做的是在遍历中丢弃不可能让面积更大的项。
假设两种极限情况,类似下面两组数据。
10,1,2,3,4,10
1,2,3,30,30,3,1,1,4
第一组是两侧的长度最长,第二组是中间有两个相邻的项最长,他们两个极限情况都是最优解。
所以我们判断的条件是,当左右距离减小时,左侧的点向右移动若长度变小,那么必然不可能是更优的解,右侧情况同样。
我们只要在同时从左侧右侧向中间寻找长度更长的线段,而且总是更短的一侧移动,当发现更长的线段时,重新判断面积并更新,直到左右两个点相遇,遍历结束。

查看了题解的思路,写的算法

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxArea = 0
        heightLen = len(height)
        #left
        l = 0
        #right
        r = heightLen - 1
        while l < r:
            #左侧小
            while l < r and height[l] < height[r]:
                #更新
                maxArea = max(maxArea, height[l] * (r - l))
                l += 1
            #右侧小
            while l < r and height[l] >= height[r]:
                #更新
                maxArea = max(maxArea, height[r] * (r - l))
                r -= 1
        return maxArea