问题描述: 给定一组非负整数数组height,每个元素表示一个垂直线段的高度,数组的索引表示线段的横坐标。找到两条线段,它们与x轴构成的容器能够容纳最多的水。也就是找到两条线段,它们之间的距离最远,同时线段的最小高度乘以距离要最大。

代码思路和解析:

  1. 初始化两个指针,left 指向数组的第一个元素(最左侧),right 指向数组的最后一个元素(最右侧)。
  2. 初始化一个变量 max 来追踪找到的最大容器面积,初始值为0。
  3. 使用一个while循环,条件是 left 指针小于等于 right 指针。
  4. 在每一次迭代中,计算当前容器的面积,即较小高度的线段高度乘以它们之间的距离,即 amin = min(height[left], height[right]) * (right - left)。
  5. 比较 amin 和 max,将较大的值赋给 max,以更新最大容器面积。
  6. 接下来,根据当前的指针位置,移动指针,使得下一次迭代时能够计算新的容器面积:
    • 如果 height[left] < height[right],则移动 left 指针向右,因为右边的线段高度更大可能会产生更大的容器面积。
    • 否则,移动 right 指针向左,因为左边的线段高度更大可能会产生更大的容器面积。
  7. 循环结束后,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; // 返回最大容器面积
}

 

更多推荐