Container With Most Water.java

M
1527960660
tags: Two Pointers, Array

#### Two Pointers
- 木桶理论。盛水的最高取决于最低的那面墙。
- 左右两墙，往中间跑动。
- 另:若一面墙已经小于另外一面，就要移动，换掉矮墙（可能下一面更高，或更低)
- 但决不能换掉当下的高墙，因为低墙已经limit的盛水的上限，若高墙移动，导致两墙之间距离减少，就注定水量更少了。（弄啥来，不能缺心眼啊）

```
/*
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.

Example
Given [1,3,2], the max area of the container is 2.

Note
You may not slant the container.

Tags Expand 
Two Pointers Array
*/

/*
Thoughts:
Start from 2 sides with 2 pointers, use those as 2 walls.

Height of water is limited by the lower wall. For example, left wall < right wall, width = right.x - left.x
	Now, if we move right wall: right--, then width = width-1, and the whole block is still limited by the lower left wall. So, this is not a good move. 
	Instead, when left wall < right wall, we move left++.
	On the other hand, if lett wall > right wall, right--.
*/
public class Solution {
    public int maxArea(int[] heights) {
    	if (heights == null || heights.length == 0) {
    		return 0;
    	}
    	int left = 0;
    	int right = heights.length - 1;
    	int maxWater = Integer.MIN_VALUE;
    	while (left < right) {
    	    int lowWall = heights[left] < heights[right] ? heights[left] : heights[right];
    		maxWater = Math.max(maxWater, (right - left) * lowWall);
    		if (heights[left] < heights[right]) {
    			left++;
    		} else {
    			right--;
    		}
    	}
    	return maxWater;
    }
}

```