盛水最多的容器

力扣第11题：盛水最多的容器

题目描述

给定一个整数数组 height ，其中 height[i] 表示第 i 条垂线的高度。找出两条线之间可以盛水的最大量，水的容量由较短的线段决定，且取决于这两条线段之间的宽度。

示例

示例 1：

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49

示例 2：

输入：height = [1,1]
输出：1

解题思路

在本题中，我们需要找到能够形成最多水的两条线段。直观的方法是使用双重循环，计算每对线段之间的面积，但这种方法的时间复杂度为 O(n^2)，在大数据量情况下效率较低。因此，我们采用双指针（Two Pointer）的方法，以优化我们的解法。

双指针法

1. 指针初始化：我们使用两个指针 left 和 right，分别指向数组的开头和结尾。
2. 面积计算：在每一步中，我们计算当前两条线段之间的面积，并更新 max_area 以保存当前的最大值。
3. 移动指针：每次比较两个指针指向的线段的高度，移动指向较短线段的指针。这是因为水的容量由较短的线段决定，移动较短线段的指针可能会找到更高的线段，进而增加面积。

这种方法确保我们只遍历数组一次，时间复杂度为 O(n)。

代码实现

#include <stdio.h>

int maxArea(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int max_area = 0;

    while (left < right) {
        int width = right - left;
        int current_height = height[left] < height[right] ? height[left] : height[right];
        int current_area = current_height * width;
        max_area = max_area > current_area ? max_area : current_area;

        // 移动指向较短线段的指针
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return max_area;
}

int main() {
    int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int size = sizeof(height) / sizeof(height[0]);
    printf("Maximum area: %d\n", maxArea(height, size)); // 输出：49
    return 0;
}

代码解释

• maxArea 函数：该函数接受一个整型数组 height 以及其大小 heightSize，返回能够盛水的最大面积。
• 双指针法实现：
  • 初始化左右指针和最大面积变量。
  • 在循环中计算当前面积，并通过条件判断更新最大面积。
  • 根据高度的比较，调整指针位置以继续寻找可能的最大面积。
• 主函数：测试该算法并打印结果，以验证其有效性。

总结

通过双指针法，我们可以有效地解决盛水最多的容器问题，时间复杂度降低至 O(n)。该方法的优势在于空间复杂度为 O(1)，不需要额外的存储空间。这种优化策略在实际应用中具有重要的价值，尤其是在处理大型数据集时。

希望这篇文章对你理解盛水最多的容器问题有所帮助，欢迎大家在评论区交流心得与体会！