Advantrue 1 - Leetcode 11 - Container With Most Water

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai)(i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

解题思路

对于这样的题目,很明显可以快速的使用brute-force方式得到解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxArea(int[] height) {
int maxArea = Integer.MIN_VALUE;
for (int i = 0; i < height; i++) {
for (int j = i+1; j < height; j++) {
int temp = (j-i) * (height[i]>height[j]?height[j]:height[i]);
if (temp > maxArea)
maxArea = temp;
}
}
return maxArea;
}
}

复杂度分析(Complexity Analysis):

  • 时间复杂度(Time complexity): O(n2)O(n^2)
  • 空间复杂度(Space complexity): O(1)O(1)

显然使用brute-force解法设计的算法是正确的,但是时间复杂度是O(n2)O(n^2)级别,因此我们需要考虑优化。
代码提交状况:
运行时间(Runtime): 269 ms
beats rate: 20.1%

其实仔细看的话,要使围成的矩形面积最大,无非就是让长和宽尽量的大,因此我们可以使用Two-pointers双指针的思想:
使用两个指针i,j分别指向0height.length-1,让一开始的x坐标距离最大化,然后判断它们所对应的高度谁低,
依据较低的高度值计算面积,再将对应索引指针增1(对于低索引指针)或减1(高索引指针)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int maxArea(int[] height) {
int maxArea = Integer.MIN_VAlUE;
int i = 0;
int j = height.length-1;
while (i < j) {
// int x = j - i;
// maxArea = Math.max(maxArea,Math.min(heigth[i], height[j])*x);
// if (height[i] < height[j]) {
// i++;
// } else {
// j--;
// }
// 对代码进行缩减
maxArea = Math.max(maxArea, height[j]<height[i]?(j-i)*height[j--]:(j-i))*height[i++]);
}
return maxArea;
}
}

复杂度分析(Complexity Analysis):

  • 时间复杂度(Time complexity): O(n)O(n)
  • 空间复杂度(Space complexity): O(1)O(1)

使用双指针,只需要一次遍历就能得到结果。可以见得双指针是非常有效的工具,也是数组类问题中常见的解题思路: 例如,对于已经排好序的两数之和(Two sum - sorted)问题,就可以使用双指针进行解决。

代码提交状况:
运行时间(Runtime): 6 ms
beat rate: 65.95%