# 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
TIP
说明：你不能倾斜容器。
来源: https://leetcode.cn/problems/container-with-most-water/ (opens new window)
解题思路:
双指针求解, 根据面积公式: S(i,j)=min(h[i],h[j])×(j−i), 不断计算面积, 最后得到最大面积
点击查看代码
/**
* 盛最多水的容器
* @param {number[]} data
* @returns number
*
* 时间复杂度 O(n)
* 空间复杂度 O(1)
*/
const maxArea = (data) => {
// 双指针
// for
// let max = 0;
// for (let i = 0, j = data.length - 1; i < j; ) {
// const minHeight = data[i] < data[j] ? data[i++] : data[j--];
// const area = (j - i + 1) * minHeight;
// console.log(`i = ${i}, j = ${j}. minHeight = ${minHeight}. area: ${area}
// (${j}-${i}+1)*${minHeight}`);
// max = Math.max(max, area);
// }
// while
let i = 0, j = data.length -1, max = 0
while(i < j) {
max = Math.max(max, Math.min(data[i], data[j]) * (j - i))
if (data[i] < data[j]) {
i++
} else {
j--
}
}
return max;
}
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))
// 49
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35