LeetCode - Medium - 11. Container With Most Water

柔情只为你懂 2023-01-01 02:51 109阅读 0赞

## Topic ##

*  Array
 *  Two Pointers

## Description ##

[https://leetcode.com/problems/container-with-most-water/][https_leetcode.com_problems_container-with-most-water]

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 the line `i` is at `(i, ai)` and `(i, 0)`. Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

**Notice** that you may not slant the container.

**Example 1**:

![8ae40936a75588238d3324740c451bad.png][]

Input: height = [1,8,6,2,5,4,8,3,7]
    Output: 49
    Explanation: 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.

**Example 2**:

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

**Example 3**:

Input: height = [4,3,2,1,4]
    Output: 16

**Example 4**:

Input: height = [1,2,1]
    Output: 2

**Constraints**:

*  n = height.length
 *  2 <= n <= 3 \* 10⁴
 *  0 <= height\[i\] <= 3 \* 10⁴

## Analysis ##

方法一：暴力算法

--------------------

方法二：双指针算法

The max area is calculated by the following formula:

S = (j - i) * min(ai, aj)

We should choose (i, j) so that S is max. Note that `i, j` go through the range (1, n) and j > i. That’s it.

The simple way is to take all possibilities of (i, j) and compare all obtained S. The time complexity is `n * (n-1) / 2`.（暴力算法）

**What we gonna do is to choose all possibilities of (i, j) in a wise way**. I noticed that many submitted solutions here can’t explain why when :

*  `ai < aj` we will check the next `(i+1, j)` (or move i to the right)
 *  `ai >= aj` we will check the next `(i, j-1)` (or move j to the left)

（也就是保留两者中最大的下标，移动最小值的下标（i的向右移动，j的向左移动））

Here is the explaination for that:

*  When `ai < aj` , we don’t need to calculate all `(i, j-1)`, `(i, j-2)`, … Why? because these max areas are smaller than our S at `(i, j)`

Assume at `(i, j-1)` we have

ai < aj
    S = (j - i) * min(ai, aj) = (j - i) * ai
    
    if aj-1 >= ai
    S' = (j - 1 - i) * min(ai, aj-1) = (j - 1 - i) * ai
    S > S'
    
    if aj-1 < ai
    S' = (j - 1 - i) * min(ai, aj-1) = (j - 1 - i) * aj-1
    S > S'
    
    So no matter aj-1 >= ai or aj-1 < ai，S' < S always true

we don’t need to calculate Similar at `(i, j-2)`, `(i, j-3)`, etc.

So, that’s why when `ai < aj`, we should check the next at `(i+1, j)` (or move i to the right)

*  When `ai >= aj`, the same thing, all `(i+1, j)`, `(i+2, j)`, … are not needed to calculate.

ai >= aj
    S = (j - i) * min(ai, aj) = (j - i) * aj
    
    if ai+1 >= aj
    S' = (j - (i + 1)) * min(ai+1, aj)
    < (j - i - 1) * aj
    S' < S
    
    if ai+1 < aj
    S' = (j - (i + 1)) * min(ai+1, aj)
    < (j - i - 1) * ai+1
    S' < S
    
    So no matter ai+1 >= aj or ai+1 < aj，S' < S always true

We should check the next at `(i, j-1)` (or move j to the left)

PS.**似非而是的解法**啊！

## Submission ##

public class ContainerWithMostWater { 
    
    	// 方法一：暴力算法
    	public int maxArea1(int[] height) { 
    		int maxCapacity = 0;
    
    		for (int i = 0; i < height.length; i++) { 
    			for (int j = i + 1; j < height.length; j++) { 
    				int min = Math.min(height[i], height[j]);
    				int distance = j - i;
    				maxCapacity = Math.max(maxCapacity, min * distance);
    			}
    		}
    		return maxCapacity;
    	}
    
    	// 方法二：双指针
    	public int maxArea2(int[] height) { 
    		int S = 0, i = 0, j = height.length - 1;
    		while (i < j) { 
    			S = Math.max(S, (j - i) * Math.min(height[i], height[j]));
    			if (height[i] < height[j])
    				i++;
    			else
    				j--;
    		}
    		return S;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class ContainerWithMostWaterTest { 
    
    	@Test
    	public void test() { 
    		ContainerWithMostWater obj = new ContainerWithMostWater();
    
    		assertEquals(49, obj.maxArea1(new int[] { 1, 8, 6, 2, 5, 4, 8, 3, 7}));
    		assertEquals(1, obj.maxArea1(new int[] { 1, 1}));
    		assertEquals(16, obj.maxArea1(new int[] { 4, 3, 2, 1, 4}));
    		assertEquals(2, obj.maxArea1(new int[] { 1, 2, 1}));
    		
    		assertEquals(49, obj.maxArea2(new int[] { 1, 8, 6, 2, 5, 4, 8, 3, 7}));
    		assertEquals(1, obj.maxArea2(new int[] { 1, 1}));
    		assertEquals(16, obj.maxArea2(new int[] { 4, 3, 2, 1, 4}));
    		assertEquals(2, obj.maxArea2(new int[] { 1, 2, 1}));
    	}
    }

[https_leetcode.com_problems_container-with-most-water]: https://leetcode.com/problems/container-with-most-water/
[8ae40936a75588238d3324740c451bad.png]: /images/20221120/56a782925d874c7983ddd74eab2c9123.png