盛最多水的容器|博客系列
# 题目描述
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例一🌰:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
@前端进阶之旅: 代码已经复制到剪贴板
示例二🌰:
输入: [6, 7, 1]
输出: 7
@前端进阶之旅: 代码已经复制到剪贴板
# 解题思路
设第一条线的下标为数组中的l, 第二条线为r;
理解容器的面积实际就是(r - l) * Math.min(height[l], height[r])的最大值.
解法一
暴力破解法(不推荐)
利用两个for循环遍历出所有的情况, 并进行比较出最大值;
解法二
双指针法:
设置双指针l和r分别位于容器的一头一尾,根据规则移动指针, 并且更新面积最大值 maxS，直到 l == r 时返回 maxS。
- 考虑输入的数组长度为
0, 1, 2的情况; - 设置双指针
l和r分别位于容器的一头一尾; - 使用
while循环, 当l == r时结束循环; - 判断每次
height[l]和height[r]的高度, 若是后者大,则指针l向前移动, 反之则移动r; - 其实本质就是在移动的过程中不断消去不可能成为最大值的状态.
# coding
解法一
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
if (!height || height.length <= 1) return 0;
const len = height.length;
if (len === 2) return Math.min(height[0], height[1]);
let maxS = 0;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
maxS = Math.max(maxS, (j - i) * Math.min(height[i], height[j]));
}
}
return maxS;
};
@前端进阶之旅: 代码已经复制到剪贴板
执行用时820ms, 内存消耗35.4MB.
解法二
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
if (!height || height.length <= 1) return 0;
const len = height.length;
if (len === 2) return Math.min(height[0], height[1]);
let maxS = 0,
l = 0,
r = len - 1;
while (l < r) {
maxS = height[l] < height[r] ?
Math.max(maxS, (r - l) * height[l++]) :
Math.max(maxS, (r - l) * height[r--]);
}
return maxS;
};
@前端进阶之旅: 代码已经复制到剪贴板
执行用时76ms, 内存消耗35.4MB.
