友情提示:文中代码格式不佳的读者们请点击阅读原文或者使用桌面版微信
1题目
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.
Example:
Input:
[1,8,6,2,5,4,8,3,7]
Output: 49
2翻译
给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。
3分析
使用贪心算法
3解法
思路一
public int maxArea(int[] height) {
// 参数校验
if (height == null || height.length < 2) {
return 0;
}
// 记录最大的结果
int result = 0;
// 左边的竖线
int left = 0;
// 右边的竖线
int right = height.length - 1;
while (left < right) {
// 设算当前的最大值
result = Math.max(result, Math.min(height[left], height[right]) * (right - left));
// 如果右边线高
if (height[left] < height[right]) {
int k = left;
// 从[left, right - 1]中,从左向右找,找第一个高度比height[left]高的位置
while (k < right && height[k] <= height[left]) {
k++;
}
// 从[left, right - 1]中,记录第一个比原来height[left]高的位置
left = k;
}
// 左边的线高
else {
int k = right;
// 从[left + 1, right]中,从右向左找,找第一个高度比height[right]高的位置
while (k > left && height[k] <= height[right]) {
k--;
}
// 从[left, right - 1]中,记录第一个比原来height[right]高的位置 right = k;
}
}
return result;
}
思路二
以上解法耗时5ms左右,算是相当快的一种方式了,但是代码较为复杂,下边提供一种代码较为简单,也比较暴力的一种解法,耗时会在10ms左右
public int maxArea(int[] height) {
int res = 0, i = 0, j = height.length - 1;
while (i < j) {
res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
if (height[i] < height[j]) ++i;
else --j;
}
return res;
}
4总结
刚才经历了正则表达匹配的难关,所以来一道稍微简单点的题,有种拨开云雾见天晴的感觉。这道题其实直接暴力解决也未尝不可,就是暴力吧,先选左边再选右边。但在此基础上加了一些优化,取左边时,若是height[i] < height[i - 1]时,就直接跳过此条左边的余下操作,因为此时无论怎么选右边,矩形面积都不会比max大。取右边时,若是右边大于等于当前左边,即height[j] >= height[i],则在比较完max后,跳过此条左边操作,因为在此条左边的情况下,之后的面积都不会比当前大了。