python 盛最多水的容器多种解法

编程小白狼

发布于 2024-12-31 08:11:16

3500

代码可运行

文章被收录于专栏：编程小白狼

运行总次数：0

代码可运行

题目描述：给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i, ai)。在坐标内画 n 条垂直线，使得线 i 的两个端点分别为(i, ai)和(i, 0)。找出其中的两条线，使得它们与 x 轴形成的容器可以容纳最多的水。

一、暴力法

思路：遍历所有可能的组合，计算每个组合对应的容积，找到最大值。

代码实现：

def maxArea(height):
    """
    :type height: List[int]
    :rtype: int
    """
    n = len(height)
    max_area = 0
    for i in range(n):
        for j in range(i+1, n):
            h = min(height[i], height[j])
            w = j - i
            area = h * w
            max_area = max(max_area, area)
    return max_area

时间复杂度：O(n^2)

二、双指针法

思路：使用两个指针分别指向数组的左右两端，计算当前两个指针所对应的容积，然后移动较短的那个指针，再次计算容积，直到两个指针相遇。

代码实现：

def maxArea(height):
    """
    :type height: List[int]
    :rtype: int
    """
    n = len(height)
    max_area = 0
    left, right = 0, n-1
    while left < right:
        h = min(height[left], height[right])
        w = right - left
        area = h * w
        max_area = max(max_area, area)
        if height[left] <= height[right]:
            left += 1
        else:
            right -= 1
    return max_area

时间复杂度：O(n)

三、优化版双指针法

思路：根据双指针法，每次移动较短的那个指针，有可能会错过最优解。因此，我们可以先计算当前两个指针所对应的容积，然后移动较短的那个指针，直到它指向比它大的位置为止。

代码实现：

def maxArea(height):
    """
    :type height: List[int]
    :rtype: int
    """
    n = len(height)
    max_area = 0
    left, right = 0, n-1
    while left < right:
        h = min(height[left], height[right])
        w = right - left
        area = h * w
        max_area = max(max_area, area)
        if height[left] <= height[right]:
            i = left
            while i < right and height[i] <= height[left]:
                i += 1
            left = i
        else:
            j = right
            while j > left and height[j] <= height[right]:
                j -= 1
            right = j
    return max_area

时间复杂度：O(n)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除

python