力扣--贪心算法11.盛最多的水
·

问题描述: 给定一组非负整数数组height,每个元素表示一个垂直线段的高度,数组的索引表示线段的横坐标。找到两条线段,它们与x轴构成的容器能够容纳最多的水。也就是找到两条线段,它们之间的距离最远,同时线段的最小高度乘以距离要最大。
代码思路和解析:
- 初始化两个指针,
left指向数组的第一个元素(最左侧),right指向数组的最后一个元素(最右侧)。 - 初始化一个变量
max来追踪找到的最大容器面积,初始值为0。 - 使用一个
while循环,条件是left指针小于等于right指针。 - 在每一次迭代中,计算当前容器的面积,即较小高度的线段高度乘以它们之间的距离,即
amin = min(height[left], height[right]) * (right - left)。 - 比较
amin和max,将较大的值赋给max,以更新最大容器面积。 - 接下来,根据当前的指针位置,移动指针,使得下一次迭代时能够计算新的容器面积:
- 如果
height[left] < height[right],则移动left指针向右,因为右边的线段高度更大可能会产生更大的容器面积。 - 否则,移动
right指针向左,因为左边的线段高度更大可能会产生更大的容器面积。
- 如果
- 循环结束后,
max包含了最大的容器面积,返回max。
int maxArea(int* height, int heightSize) {
int left = 0; // 初始化左指针
int right = heightSize - 1; // 初始化右指针
int max = 0; // 初始化最大容器面积为0
while (left <= right) { // 开始双指针遍历
int amin = min(height[left], height[right]) * (right - left); // 计算当前容器面积
max = max >= amin ? max : amin; // 更新最大容器面积
if (height[left] < height[right]) {
left++; // 移动左指针向右
} else {
right--; // 移动右指针向左
}
}
return max; // 返回最大容器面积
}
更多推荐



所有评论(0)