LeetCode11-Container With Most Water

两点法,规定两点构建初始枚举范围,然后通过题目特点,移动(舍弃)其中一点,缩小枚举范围,直至不能继续枚举。比较过程中产生的结果值,得到正确答案。

链接: https://leetcode.com/problems/container-with-most-water/

题面

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

示意图
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.

题意

n 个非负整数 a1, a2, a3, …, an,分别表示 n 个不同高度的垂直线,水平间隔为 1。 面积等于两根垂直线之间的水平距离与短边构成的矩形面积。求最大面积。

方法

暴力

在 LeetCode 上,这道题通过两两暴力枚举是可以 AC 的,复杂度 O(N^2),暴力就没啥好说的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxArea(vector<int>& height) {
int maxA = 0;

int len = height.size();
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
int a = (j - i) * min(height[j], height[i]);
maxA = max(a, maxA);
}
}

return maxA;
}

两点法

矩形面积由两边之间水平长度和短边高度决定,而这个方法就是利用不断缩小两边水平长度、舍弃短边,枚举最大面积。

首先,分别以最左和最右两条垂直线为左右两边的端点,计算面积,然后移动短边所在端点,向中间靠近一个单位,计算新的面积,与之前面积比较并取大。

之所以移动短边端点,而不移动长边端点,是因为进一步枚举,势必缩短水平长度,如果移动长边,矩阵高度只会保持或减小,所以面积只可能缩小;而移动短边,矩阵高度可能会增加,虽然水平长度减小,但面积仍有可能增大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxArea(vector<int>& height) {
int maxA = 0;
int l = 0;
int r = height.size() - 1;

while (l < r) {
int a = (r - l) * min (height[l], height[r]);
maxA = max(a, maxA);
if (height[l] < height[r])
l++;
else
r--;
}

return maxA;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×