0%

leetcode 11 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. 题目地址:leetcode Container With Most Water

题目大意: 给定n个数a1~an,代表垂直x轴的线的高度。求任意两条线之间所能装水的最大容积。容积的计算方式为 min(ai,aj) * (j - i) ,  i < j

思路:

简单的做法是直接枚举起点i和终点j,然后计算一次min(ai,aj) * (j - i),取最大,这样复杂度O(n^2)

更好的做法是双指针,这样可以达到O(n).

一开始l和r分别指向首尾,即l = 0, r = len(a) - 1,  然后计算容积。 接着若a[l] < a[r] 则 l++ 否则 r--

为啥是对的? 看看公式min(ai,aj) * (j - i) ,  若 a[l] < a[r],只能通过增加二者中较小的a[l]来增加面积,因为j - i已经是目前能达到的最大值了。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxArea(vector<int>& height) {
int ans = 0;
for(int i = 0, j = height.size() - 1; i < j;){
if(height[i] < height[j])
ans = max((j - i) * height[i++], ans);
else
ans = max((j - i) * height[j--], ans);
}
return ans;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxArea(int[] height) {
int ans = 0;
for (int l = 0, r = height.length - 1; l < r; ) {
ans = Math.max(ans, (r - l) * Math.min(height[l], height[r]));
if (height[l] < height[r])
l++;
else
r--;
}
return ans;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
ans = l = 0
r = len(height) - 1
while l < r:
ans = max(ans, (r - l) * min(height[l], height[r]))
if height[l] < height[r]:
l += 1
else:
r -= 1
return ans

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~