11. Container with the most water

Simple thinking , Clear code .

subject

link ：https://leetcode-cn.com/problems/container-with-most-water

Here you are. n Nonnegative integers a1,a2,…,an, Each number represents a point in the coordinate (i, ai) . Draw in coordinates n Bar vertical line , Vertical line i The two endpoints of are (i, ai) and (i, 0) . Find two of them , Make them x A container of shafts can hold the most water .

explain ： You can't tilt the container .

Example 1：

 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

Example 3：

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

Example 4：

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

Tips ：

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

Topic analysis

This question , Think of array elements as boards of containers , The difference between subscripts is regarded as the length of the container .

The amount of water in the container = Height of short board * The difference between subscripts

The simplest rough solution is a double loop ：

1. The outer loop , Subscript i Fix the board on the left height[i]
2. Inner circulation moves j , Get the board on the right height[j]
3. The height of the water depends on the shorter board , So take height Smaller value , Multiply by the difference between subscripts (j - i)
4. Compare the obtained number with the result calculated before , Take the larger value . Finally, we get the result

class Solution {
    
    public int maxArea(int[] height) {
    
        int ans = 0;
        for (int i = 0; i < height.length ; i++) {
    

            for (int j = height.length - 1; j > i;  j--) {
    
                int v = Math.min(height[i],height[j]) * (j-i); //  Current water capacity 
                ans = Math.max(ans , v); //  Take a large amount of water 
            }

        }
        return ans;
    }
}

Double pointer optimization

Optimize the solution just now , The idea of optimization must be to reduce a cycle .
Hot topics like this interview , There is usually a solution that comes to mind at a glance , And finally after optimization O(n) Solution method .
After all , The interviewer will not choose a question without skills .

The disadvantage of violence law is for a cycle , Move the plank in only one direction . And the double pointer can achieve a cycle , Move the plank in both directions . Move height Smaller pointer .

Let me give an example to understand the idea of double pointer , I take the example of the topic 1 To illustrate ：

1. height[0] It's the shortest board , The value is 1
2. The law of violence above , It's from right to left , Move the template on the right . The template on the right is subscript 8, Move to the left .
3. The first calculation is height[0] * (8 - 0) = 8 , It is the outer cycle for height[0] The maximum of ; Continue to move the right j, Move left to 7 ,height[0] * (7 - 0) = 7, Predictably, , It will only get smaller and smaller .
4. There is no need to move the subscript of the right subscript , Instead, move the left subscript , send i Move to 1 The location of . because height[1] Than height[8] Big , take height[8] As a height , Calculation height[8] * (8 - 1) = 49.

Sum up , Just now i = 0 when , No matter how we move the right pointer , The capacity of the container obtained is less than that of the container before moving , So move the left pointer . therefore , The solution of double pointer is , Each move height Smaller subscripts .

class Solution {
    
    public int maxArea(int[] height) {
    
        int i = 0;
        int j = height.length - 1;
        int ans = 0;
        while (i < j) {
    
            int result = Math.min(height[i], height[j]) * (j - i);
            ans = Math.max(ans, result);
            if (height[i] < height[j]) {
    
                i++;
            } else {
    
                j--;
            }
        }
        return ans;
       
    }
}

Recommend to see LeetCode The official solution to this problem
This is the end of this article.