这是悦乐书的第350次更新，第375篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Medium级别的第5题（顺位题号是11）。给定n个非负整数a1，a2，…，an，其中每个表示坐标（i，ai）处的点。绘制n条垂直线，使得线i的两个端点位于（i，ai）和（i，0）。找到两条线，它们与x轴一起形成一个容器，这样容器就含有最多的水。
注意：您可能不会倾斜容器，n至少为2。
image
上面的垂直线由数组[1,8,6,2,5,4,8,3,7]表示。 在这种情况下，容器可容纳的最大水面积（蓝色部分）为49。例如：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
02 第一种解法
暴力解法，使用两层循环，装水容器的宽为两元素索引之差，高为两元素中的较小值，利用宽乘以高，计算容器的面积，取其中较大值返回。
此解法的时间复杂度是O(N^2)，空间复杂度为O(1)。
public int maxArea(int[] height) {
int result = 0, n = height.length;
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
int w = j-i;
int h = Math.min(height[i], height[j]);
result = Math.max(result, w*h);
}
}
return result;
}
03 第二种解法
双指针。定义两个变量，一个从数组的头部开始，记为start，另外一个从尾部开始，记为end，依旧按照第一种解法中那样计算面积和取最大值，然后来判断哪个指针该往哪个方向移动。
如果start位置的元素值小于end位置的元素值，那么start位置需要找到一个更大的值，才有可能比当前的面积大，所以start需要自增1，向end方向移动，反之就是end位置需要向start位置方向移动，来找到一个更大的元素值。
此解法的时间复杂度是O(N)，空间复杂度为O(1)。
public int maxArea2(int[] height) {
int start = 0, end = height.length-1;
int result = 0;
while (start < end) {
int w = end - start;
int h = Math.min(height[end], height[start]);
result = Math.max(result, w*h);
if (height[start] < height[end]) {
start++;
} else {
end--;
}
}
return result;
}
04 第三种解法
如果你觉得第二种解法中，没有讨论两边的元素相等时的情况，那咱也可以再多加一个判断。
public int maxArea3(int[] height) {
int start = 0, end = height.length-1;
int result = 0;
while (start < end) {
int w = end - start;
int h = Math.min(height[end], height[start]);
result = Math.max(result, w*h);
if (height[start] < height[end]) {
start++;
} else if(height[start] > height[end]) {
end--;
} else {
start++;
end--;
}
}
return result;
}
05 小结
算法专题目前已连续日更超过六个月，算法题文章218+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论