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思想