【LeetCode】11. Container With Most Water

1.题目描述

　　Given n non-negative integers a₁, a₂, …, a_n , where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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 and n is at least 2.

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

说明：你不能倾斜容器，且 n 的值至少为 2。

　　The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

2.理解

　　The O(n) solution with proof by contradiction doesn’t look intuitive enough to me. Before moving on, read any example of the algorithm first if you don’t know it yet.

　　Here’s another way to see what happens in a matrix（矩阵） representation:

　　Draw a matrix where the row is the first line, and the column is the second line. For example, say n=6.

　　In the figures below, x means we don’t need to compute the volume for that case: (1) On the diagonal（对角线）, the two lines are overlapped（重叠）; (2) The lower left triangle area of the matrix is symmetric（对称） to the upper right area.

　　We start by computing the volume at (1,6), denoted（记） by o. Now if the left line is shorter than the right line, then all the elements left to (1,6) on the first row have smaller volume, so we don’t need to compute those cases (crossed by ---).

  1 2 3 4 5 6
1 x ------- o
2 x x
3 x x x 
4 x x x x
5 x x x x x
6 x x x x x x

　　Next we move the left line and compute (2,6). Now if the right line is shorter, all cases below (2,6) are eliminated（消除、淘汰）.

  1 2 3 4 5 6
1 x ------- o
2 x x       o
3 x x x     |
4 x x x x   |
5 x x x x x |
6 x x x x x x

　　And no matter how this o path goes, we end up only need to find the max value on this path, which contains n-1 cases.

  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x

　　Hope this helps. I feel more comfortable seeing things this way.

3.Solutions

　　AKA, the general idea to find some max is to go through all cases where max value can possibly occur and keep updating the max value. The efficiency of the scan depends on the size of cases you plan to scan.

　　To increase efficiency, all we need to do is to find a smart way of scan to cut off the useless cases and meanwhile 100% guarantee the max value can be reached through the rest of cases.

　　In this problem, the smart scan way is to set two pointers（双指针） initialized at both ends of the array. Every time move the smaller value pointer to inner array. Then after the two pointers meet, all possible max cases have been scanned and the max situation is 100% reached somewhere in the scan. Following is a brief prove of this.

　　Given a₁,a₂,a₃…..a_n as input array. Lets assume a₁₀ and a₂₀ are the max area situation. We need to prove that a₁₀ can be reached by left pointer and during the time left pointer stays at a₁₀, a₂₀ can be reached by right pointer. That is to say, the core problem is to prove: when left pointer is at a₁₀ and right pointer is at a₂₁, the next move must be right pointer to a₂₀.

　　Since we are always moving the pointer with the smaller value, i.e. if a₁₀ > a₂₁, we should move pointer at a₂₁ to a₂₀, as we hope. Why a₁₀ >a₂₁? Because if a₂₁>a₁₀, then area of a₁₀ and a₂₀ must be less than area of a₁₀ and a₂₁. Because the area of a₁₀ and a₂₁ is at least height[a₁₀] (21-10) while the area of a₁₀ and a₂₀ is at most height[a₁₀] (20-10). So there is a contradiction（矛盾） of assumption a₁₀ and a₂₀ has the max area. So, a₁₀ must be greater than a₂₁, then next move a₂₁ has to be move to a₂₀. The max cases must be reached.

public static int maxArea(int[] height) {
	    int left = 0, right = height.length - 1;
		int maxArea = 0;

		while (left < right) {
			maxArea = Math.max(maxArea, Math.min(height[left],height[right])
                               * (right-left));
			if (height[left] < height[right])
				left++;
			else
				right--;
		}
		return maxArea;
	}

（完）