LeetCode第十一题：盛最多水的容器

admin
学习
2023-09-20
53热度
0评论

题目来源：LeetCode第十一题

1.题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]

输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

提示：

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

2.解题思路

解法一：暴力法

描述：遍历所有两条线之间的蓄水面积找到最大值。
时间复杂度：O(n^2)。使用了两层循环来遍历所有可能的线条组合。
空间复杂度：O(1)。我们没有使用任何与输入规模n成比例的额外存储空间。
参考代码：

java代码：

class Solution {
    public int maxArea(int[] height) {
        // 最大面积
        int maxArea = 0;
        // 通过双层循环来找到每两个线之间的蓄水面积
        for (int i = 0; i < height.length - 1; i++) {
            for (int j = i + 1; j < height.length; j++) {
                // 这是两条线围成的宽
                int width = j - i;

                // 找到两个线之间短的那一个，因为两条线之间的蓄水面积取决于短的那个
                int minHeight = Math.min(height[i], height[j]);

                // 计算面积最大值
                maxArea = Math.max(maxArea, width * minHeight);
            }
        }
        return maxArea;
    }
}

C++版：

class Solution {
public:
	int maxArea(vector<int>& height)
	{
		int maxArea = 0;
		// 外层循环，遍历每一条线条
		for (int i = 0; i < height.size() - 1; i++)
		{
			// 内层循环，与外层循环形成的线条组成一对
			for (int j = i + 1; j < height.size(); j++)
			{
				// 这是两条线围成的宽
				int width = j - i;
				// 找到两个线之间短的那一个，因为两条线之间的蓄水面积取决于短的那个
				int minHeight = min(height[i], height[j]);
				// 计算面积最大值
				maxArea = max(maxArea, width * minHeight);
			}
		}
		return maxArea;
	}
};

C版：

int maxArea(int* height, int heightSize) {
	int maxArea = 0;

	// 外层循环，遍历每一条线条
	for (int i = 0; i < heightSize - 1; i++) {
		// 内层循环，与外层循环形成的线条组成一对
		for (int j = i + 1; j < heightSize; j++) {
			// 计算两条线之间的距离
			int width = j - i;

			// 找出两条线中的较短者
			int minHeight;
			if (height[i] < height[j]) {
				minHeight = height[i];
			}
			else {
				minHeight = height[j];
			}

			// 计算容纳的水量，并更新最大值
			if (width * minHeight > maxArea) {
				maxArea = width * minHeight;
			}
		}
	}
	return maxArea;
}

解法二：双指针法

描述：用两个指针指向数组的开始和结尾。在每一步中，计算两个指针指向的线段构成的容器的面积。观察两个指针指向的线段的长度，移动较短的那个指针。因为如果移动较长的那条线，宽度减小，而高度仍然由较短的线段决定，所以面积只会减少或保持不变。
时间复杂度：O(n)。双指针方法只需要线性时间就能检查所有可能的容器。因为数组中的每个元素都只被访问一次
空间复杂度：O(1)。我们只使用了几个额外的变量。
参考代码：

java版：

class Solution {
    public int maxArea(int[] height) {
        // 用两个指针指向数组的两端
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        // 当两个指针相遇时，算法结束。
        while (left < right) {
            // 算出两条线的高度和宽度，来计算面积
            int h = Math.min(height[left], height[right]);
            int w = right - left;

            maxArea = Math.max(maxArea, h * w);
            // 每次都移动指向较短线的指针，因为移动较长线的指针不会增加面积
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

C++版：

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        // 用两个指针指向数组的两端
        int left = 0;
        int right = height.size() - 1;
        int maxArea = 0;
        // 当两个指针相遇时，算法结束。
        while (left < right)
        {
            // 算出两条线的高度和宽度，来计算面积
            int h = min(height[left], height[right]);
            int w = right - left;

            maxArea = max(maxArea, h * w);
            // 每次都移动指向较短线的指针，因为移动较长线的指针不会增加面积
            if (height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return maxArea;
    }
};

C版：

int maxArea(int* height, int heightSize) {
	// 定义两个指针，从数组的两端开始
	int left = 0;
	int right = heightSize - 1;
	int maxArea = 0;  // 用于存储最大面积

	// 当left指针仍在right指针的左侧时继续
	while (left < right) {
		// 计算当前面积
		// 高度由两条线中的较短的那条决定
		int h = height[left] < height[right] ? height[left] : height[right];
		int w = right - left;  // 宽度为两个指针的距离
		int area = h * w;     // 当前面积
		maxArea = maxArea > area ? maxArea : area;  // 更新最大面积

		// 移动指向较短线的指针，以增加找到更大面积的可能性
		if (height[left] < height[right]) {
			left++;
		}
		else {
			right--;
		}
	}

	return maxArea;
}