【leetcode】11 盛水最多的容器（python实现）

【leetcode】11 盛水最多的容器（python实现）

目录

题目（中等）

分析

代码

参考

---

题目（中等）

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

说明：你不能倾斜容器

分析

方法1：暴力解法，两次遍历，取最大的面积。

方法2：双指针。以双指针作为左右的边界，l为初始下标为1，r初始下标为n-1，通过比较height[l]和height[r]的大小，来确定指针的移动，若height[l] < height[r],左指针向右移动一位，相反，右指针向左移动一位。每次移动的都是短边，因为计算时是以短边参与计算的，我们要找到尽可能长的短边，所以移动长边没有意义。

复杂度分析

时间复杂度：O(N)，双指针总计最多遍历整个数组一次。

空间复杂度：O(1)，只需要额外的常数级别的空间。

代码

方法1：两次遍历

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        for i in range(n):
            for j in range(i+1,n):
                area = min(height[j],height[i]) * (j-i)
                ans = max(ans,area)
        return ans

结果：
超出时间限制；

方法2：双指针
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        l,r = 0,n-1
        while l < r:
            area = min(height[l],height[r]) * (r-l)
            ans = max(area,ans)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

结果：
执行用时：192 ms, 在所有 Python3 提交中击败了53.42%的用户
内存消耗：24.4 MB, 在所有 Python3 提交中击败了5.43%的用户

参考

11. 盛最多水的容器 - 力扣（LeetCode） (leetcode-cn.com)

点个赞吧！

The end!