附JSPythonC题解Leetcode-面试150题8
目录
【附JS、Python、C++题解】Leetcode 面试150题（8）
一、题目
给定一个长度为
n
的整数数组
height
。有
n
条垂线，第
i
条线的两个端点是
(i, 0)
和
(i, height[i])
。
找出其中的两条线，使得它们与
x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。你不能倾斜容器。
二、思路
容纳最多的水——(j-i) * min(height[i], height[j])取到最大值
如果直接遍历下去，要比较的次数太多了（也就是指针移动的次数太多了），怎么办呢？
我们要找到简化比较过程的一个规律，可以利用最大储水量依赖的容器高来判断指针如何移动：
1. 初始化两个指针
：
left
指向数组的开头，
right
指向数组的末尾。
2. 初始化最大水量
：
most
用于存储最大的水量。
3. 循环条件
：当
left
小于
right
时，继续循环。
4. 计算当前水量 ：
h是两个高度中的较小值。width是两个指针之间的距离。water是当前容器可以容纳的水量。
5. 更新最大水量
：用
Math.max
更新
most
。
6. 移动指针 ：
- 如果
height[left]小于height[right]，增加left指针。 - 否则，减小
right指针。
7. 返回最大水量
：
在循环结束后返回
most
。
三、代码
① JavaScript：
function mostWater(height) {
let left = 0;
let right = height.length - 1;
let most = 0;
while (left < right) {
const h = Math.min(height[left], height[right]);
const width = right - left;
const water = h * width;
most = Math.max(most, water);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return most;
};② python：
def most_water(height):
left = 0
right = len(height) - 1
most = 0
while left < right:
h = min(height[left], height[right])
width = right - left
water = h * width
if water > most:
most = water
if height[left] < height[right]:
left += 1
else:
right -= 1
return most③ C++：
int mostWater(const vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int most = 0;
while (left < right) {
int h = min(height[left], height[right]);
int width = right - left;
int water = h * width;
if (water > most) {
most = water;
}
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return most;
}四、反思
上面的代码与下面自己写的代码相比，直接用max方法处理了most和water的判断，简化了步骤，学习！