11. 盛最多水的容器

🟠   🔖  贪心 数组 双指针  🔗 力扣 LeetCode

题目

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]

Output: 1

Constraints:

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

题目大意

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

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

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

说明：你不能倾斜容器。

解题思路

这一题可以用对撞指针的思路，首尾分别 2 个指针，每次移动以后都分别判断长宽的乘积是否最大。

从示例中可以看出，如果确定好左右两端的直线，容纳的水量是由 左右两端直线中较低直线的高度 * 两端直线之间的距离 所决定的。所以我们应该使得 较低直线的高度尽可能的高，这样才能使盛水面积尽可能的大。

可以使用对撞指针求解，移动较低直线所在的指针位置，从而得到不同的高度和面积，最终获取其中最大的面积。具体做法如下：

1. 使用两个指针 left，right。left 指向数组开始位置，right 指向数组结束位置。
2. 计算 left 和 right 所构成的面积值，同时维护更新最大面积值。
3. 判断 left 和 right 的高度值大小。
   1. 如果 left 指向的直线高度比较低，则将 left 指针右移。
   2. 如果 right 指向的直线高度比较低，则将 right 指针左移。
4. 如果遇到 left == right，跳出循环，最后返回最大的面积。

代码

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
	let left = 0;
	let right = height.length - 1;
	let _height, width;
	let max = 0;
	while (left < right) {
		width = right - left;
		if (height[left] > height[right]) {
			_height = height[right];
			right--;
		} else {
			_height = height[left];
			left++;
		}
		max = Math.max(max, _height * width);
	}
	return max;
};

相关题目

题号	标题	题解	标签	难度
42	接雨水	[✓]	栈 数组 双指针 2+
2517	礼盒的最大甜蜜度		贪心 数组 二分查找 1+
2560	打家劫舍 IV		数组 二分查找