# 每日一题（8）：盛最多水的容器
# 开始
今天这道题看上去是真简单
做也是真5分钟做出来了...
但时间复杂度直接O(n*(n-1))
想了许久优化方案，都没能把双层for优化掉
只能跳过几步，基本上没有质变
实在绷不住了
偷瞄了一眼题解，顿时恍然大悟
双指针
[1, 8, 6, 2, 5, 4, 8, 3, 7]
左指针指向1，右指针指向7
容水量 = min(1, 7) * 8 = 8
那么我要使容水量更多的话，移动哪根指针会更可能发生呢？
由于取的是min
所以是值较小的指针，也就是左指针
如此往复
走过n步后，那个全局最大值49，就是答案了
那么为什么可以这样做呢？
题解有详细证明过程，此处不做赘述，直接贴了
代码如下：
class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
int i = 0;
int j = height.length - 1;
while (i != j) {
int minHeight = Math.min(height[i], height[j]);
int distance = j - i;
int area = minHeight * distance;
maxArea = Math.max(area, maxArea);
if (height[i] <= height[j]) {
i++;
} else {
j--;
}
}
return maxArea;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
这次就不贴执行用时了，毕竟不是自己的成果，再香也不行
明天继续