Array - 11. Containers with the most water

1 Title Description

11. Container for the most water
    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 .

2 Title Example

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

3 Topic tips

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

4 Ideas

The area of the matrix is related to two factors ：

The length of the matrix ： The distance between two vertical lines
The width of the matrix ： The length of the shorter of the two vertical lines
therefore , To maximize the area of the matrix , The farther the two vertical lines are, the better , The shortest length of two vertical lines should be as long as possible .

We set two pointers left and right, Point to the leftmost and rightmost ends of the array respectively . here , The distance between the two vertical lines is the farthest , If the area of the next matrix is larger than the current area , We must height[left] and height[right] The shorter vertical line moves towards the middle , See if you can find a longer vertical line .

For this kind of problem , Don't think about the whole , Instead, think about the parts ; The essence is dynamic planning thinking , Consider how to deal with every sub problem, that is ： Location i, How much water can it hold .

5 My answer

 /** *  Double pointer solution  *  The time complexity is reduced  O(N), Spatial complexity  O(1) */
    public int maxArea(int[] height) {
    
        int size = height.length;
        int result = 0;
        int left_max = 0, right_max = 0;
        int left = 0, right = size - 1;

        while (left < right) {
    
            left_max = Math.max(left_max, height[left]);
            right_max = Math.max(right_max, height[right]);

            int currentArea = 0;
            // use  left  and  right  The two pointers shrink from both ends to the center , Calculate while shrinking  [left, right]  The rectangular area between , Taking the largest area value is the answer 
            // The height of the rectangle is determined by  min(height[left], height[right])  That is, determined by the lower side ：
            // Move the lower side , That side may get higher , Make the height of the rectangle larger , And then 「 There may be 」 Make the area of the rectangle larger .
            if (left_max < right_max) {
    
                currentArea = left_max * (right - left);
                left++;
            } else {
    
                currentArea = right_max * (right - left);
                right--;
            }
            result = Math.max(result, currentArea);

        }

        return result;
    }