leetcode面试准备:Container With Most Water

时间:2024-08-25 00:06:02

leetcode面试准备:Container With Most Water

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.

接口: public int maxArea(int[] height);

2 思路

题意

在二维坐标系中,(i, ai) 表示 从 (i, 0) 到 (i, ai) 的一条线段,任意两条这样的线段和 x 轴组成一个木桶,找出能够盛水最多的木桶,返回其容积。

解法

两层 for 循环的暴力法会超时。

有没有 O(n) 的解法?

答案是有,用两个指针从两端开始向中间靠拢,如果左端线段短于右端,那么左端右移,反之右端左移,知道左右两端移到中间重合,记录这个过程中每一次组成木桶的容积,返回其中最大的。(想想这样为何合理?)

把实例{ 4, 6, 2, 6, 7, 11, 2 }走一遍,可以明白。

复杂度: Time:O(n) Space:O(1)

3 代码

	/*
* 两边夹逼
* Time:O(n) Space:O(1)
*/
public int maxArea(int[] height) {
int len = height.length;
int left = 0, right = len - 1;
int res = 0;
while (left < right) {
int local = Math.min(height[left], height[right]) * (right - left);
res = Math.max(res, local);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}

4 总结

Two Pointer思想