每天学python-盛最多水的容器_盛最多水的容器python

题目：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

解题思路：

这道题可以使用双指针法来解决。我们用 i 和 j 分别表示数组的左右两端，初始化时 i = 0，j = n-1。容器的宽度为 j-i，高度为 height[i] 和 height[j] 中的较小值。因此，最大的储水量就是 (j-i) * min(height[i], height[j])。

接下来我们考虑如何移动指针。由于容器的面积取决于底部和较短的高度，因此如果 height[i] < height[j]，那么将 i 向右移动并更新最大储水量；否则，将 j 向左移动并更新最大储水量。这个过程一直持续到 i 和 j 相遇为止。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        i, j = 0, n - 1
        ans = 0
        while i < j:
            h = min(height[i], height[j])
            ans = max(ans, (j - i) * h)
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return ans

总结：

这道题是一道经典的双指针问题，又称为盛水最多的容器问题。使用双指针法可以将时间复杂度优化到 O(n)，空间复杂度为 O(1)。

双指针法通常适用于满足以下条件的问题：

1. 问题的解可以表示为两个指针之间的某种关系；
2. 指针可以根据题目要求移动，以便逼近解；

这类问题的时间复杂度通常为 O(n)，空间复杂度为 O(1)，是比较高效的算法。

总之，掌握双指针法对于解决数组和字符串相关的问题非常重要，这类问题在实际工作中也经常会遇到。