题目:11. 盛最多水的容器
如果您已经有思路了,或者是N刷了,可以先自己写一遍。
题目分析
盛最多水的容器问题要求找出两个数组索引,使得它们与x轴共同构成的容器可以容纳最多的水。
这个问题可以使用双指针两头夹逼法高效解决,就是定义两个指针,从两头向中间靠拢的方法,具体看以下解题思路说明。
解题思路
- 初始化两个指针,一个在数组的开始(称为
left
),另一个在数组的末尾(称为right
)。 - 计算当前
left
和right
指向的板子形成的容器的容量,更新最大容量。 - 移动
left
和right
中指向较短板子的那个指针向另一个指针方向移动一位(因为如果移动较长的板子,容器的宽度会减小,而容器的高度不会因为较长的板子的移动而增加,所以不可能获得更大的容量)。 - 重复步骤2和3,直到
left
和right
相遇。
Java解法
下面是使用Java语言的解法:
1 | public class Solution { |