LeetCode11-盛水最多的容器

LeetCode11-盛水最多的容器

初次想法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 超时 时间复杂度O^2
*
* @param height
* @return
*/
public int maxArea(int[] height) {
int max = 0;
for (int i = 0; i < height.length - 1; i++) {
for (int j = i + 1; j < height.length; j++) {
int area = _getArea(i, j, height);
max = Math.max(max, area);
}
}
return max;
}

private int _getArea(int i, int j, int[] height) {
return (j - i) * Math.min(height[i], height[j]);
}

双指针解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 双指针解法
*
* @param height
* @return
*/
public int maxArea2(int[] height) {
int l = 0, r = height.length - 1;
int max = 0;
while (l < r) {
int minHeight = height[l] < height[r] ? height[l++] :height[r--];
int area = (r - l + 1) * minHeight;
max = Math.max(area, max);
}
return max;
}