Preface

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 .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/container-with-most-water
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

One 、 Their thinking

Assume no duplicate values first , The left and right pointers are bigger than the right , Who accounts for the amount of water
The answer is to calculate the maximum value of all water volume in the process of drawing two left and right pointers in turn

It is not strictly required that every number can accurately calculate its answer
It only cares about the possibility of pushing up the answer
Why don't you know how to do this problem ? But look at the amount of data , You know you'll make one O(N) Solution , It is bound to think of double pointers , Whoever moves a lot and who moves a little will try this problem again , Don't know why it's possible to guess

Pictured , Move the small pointer , Water volume per calculation , Don't miss the answer

Just focus on the possibility that it pushes up the answer , But we don't strictly entangle the value of each position , What is the specific answer

Code

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

summary

Array problem encountered , And the data volume of the topic requires the use of O(n) Solution , We can consider using double pointers
We can compare the number of two pointers , Think about how to move the pointer
In this question , We found that whoever moves a little can get the answer