题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
【来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/container-with-most-water】
双指针-对撞指针
对撞指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用者相反方向的指针进行扫描,从而达到相应的目的。
指针位置
第一个指针的初始位置在遍历对象(如nums)的第一个元素,即i = 0;
另一个指针的初始位置在遍历对象(如nums)的最后一个元素,即j = len(nums) - 1.
指针移动
位于首位的指针i向右边移动一个位置,即i += 1;
位于末位的指针j向右边移动一个位置,即j -= 1。
结束条件
指针i和指针j相遇。
分析:
首先初始化双指针 i , j 分列水槽左右两端,移动双指针,通过循环将nums进行收缩,直至双指针相遇(i==j)时跳出。定义一个ans储存每个阶段得到的最大值,遍历结束后,返回最后更新的ans。
源代码
class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height) - 1
ans = 0
while i < j:
if height[i] < height[j]:
ans = max(ans, height[i] * (j - i))
i += 1
else:
ans = max(ans, height[j] * (j - i))
j -= 1
return ans