LeetCode刷题DAY 18：盛水最多的容器---三猫

难度：中级 关键词：双指针

⭐️⭐️⭐️⭐️

1

题目描述

给定一个有 n 个非负整数的数组[a1，a2，...，an]，其中每个数代表坐标中的一个点 (i, ai) ，分别与x轴做垂线，找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水，输出面积。如下图所示，给定一个数组[3,9,3,4,7,2,12,6]，其中两条绿色线与x轴构成的容器可容纳最多水，因此输出45。

2

题解

思路：双指针

本题的难点是想到双指针和想到如何移动指针。

双指针：题目中涉及到两根线，并且有左右之分，因此想到双指针。如何移动指针：面积=距离*最短边长度，想求得最大面积受限于两个维度：两根线距离和最短的线长度。两根线越远越好，因此首先将左右指针指向两端，使得从距离最长的情况开始计算；其次，把两条边中最短的替换掉才有增加面积的可能，因此移动长度小的那端指针。class Solution: def maxArea(self, height: List[int]) -> int: i = 0 j = len(height)-1 area = min(height[i],height[j])*j while i<j: if height[i]>=height[j]: j -=1 else: i += 1 if min(height[i],height[j])*(j-i)>area: area = min(height[i],height[j])*(j-i) return area ---来自腾讯云社区的---三猫