[leetcode] 11. Container with the most water

11、 Container for the most water

subject ：

Given a length of n Array of integers for height . Yes n Vertical line , The first i The two ends of the line are (i, 0) and (i, height[i]) .

Find two of them , Make them x A container of shafts can hold the most water .

Return the maximum amount of water that the container can store .

explain ： You can't tilt the container .

 Input ：[1,8,6,2,5,4,8,3,7]
 Output ：49 
 explain ： The vertical line in the figure represents the input array  [1,8,6,2,5,4,8,3,7]. In this case , The container can hold water （ In blue ） The maximum value of is  49.

Example 2：

 Input ：height = [1,1]
 Output ：1

Tips ：

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

Their thinking ：

Take a closer look at the following example 1 Graph , Discovery is to find the largest area of the area . The title also said a lot of nonsense .
In a word ： Find the largest group (i,j), bring Area Maximum ;

Dynamic programming and double pointers are needed here , The basic expression is ：
Area = Max(min(height[i], height[j]) * (j-i)) { among 0 <= i < j < height,size()};

1. Using two Pointers , The pointer with a small value moves inward , This reduces the search space
2. Because the area depends on the product of the distance of the pointer and the small value
3. If the larger value moves inward , The distance must be reduced
4. The other multiplier of the area must be less than or equal to the smaller value , Therefore, the area must be reduced
5. And we require the largest area , Therefore, the pointer with large value does not move , The pointer with small value moves inward

Reference code ：

class Solution {
    
	public int maxArea(int[] a) {
    
		 int max = 0;
		 for(int i = 0, j = a.length - 1; i < j ; ){
    
			 int minHeight = a[i] < a[j] ? a[i ++] : a[j --];
			 max = Math.max(max, (j - i + 1) * minHeight);
		 }
		 return max;
	 }
}