Double pointer advanced -- leetcode title -- container with the most water

Topic link

11. Container for the most water - Power button （LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/container-with-most-water/ My first thought on this question is Sliding window algorithm , Because I used to benefit from it

Three in a row --- Sliding window algorithm ---leetcode_emo~~~~ The blog of -CSDN Blog https://blog.csdn.net/qq_61567032/article/details/123878549?spm=1001.2014.3001.5501 Just like this. ： Everyone is simple

int maxArea(vector<int>& height) {
    int len = height.size();
    int maxx = 0;
    vector<int>ret = height;
    sort(ret.begin(), ret.end());
    int s = ret[len - 1];
    for (int i = len; i > 1; i--)
    {
        int left = 0;
        int right = left + i - 1; 
        while (right <= len - 1)
        {
            int h = min(height[left], height[right]);
            int l = i - 1;  // The length is the number of spaces between two lines ！！！
            maxx = max(maxx, h * l);
            left++;
            right++;
        }
    }
    if (s >= maxx)
        return s;
    else
        return maxx;
}

Simple is simple , Look at the time complexity , No unexpected overtime ！！

  In optimization , Inadvertently thought of the double pointer , This problem can be solved quickly through the forward and backward traversal of double pointers ;

1、 Let's start with the longest , Just don't need to judge many times every time

2、 Determine the size of the left and right pointers , Move only the smaller pointer at a time , because , If you move the big pointer , The back area will only be smaller than now ( Obviously , Due to the length from large to small , So the big pointer can only move to the left . If you move the big pointer to the left , The length of the container is reduced , But now the real length of the container （ Little pointer ） No change , So the height of the container will not increase , Therefore, the volume of the moving large pointer container only decreases but does not increase ！）

3、 Compare and select the maximum container volume , When the traversal is complete , That's the answer
 

Actually , This problem is a classic double pointer algorithm problem ！

int maxArea(vector<int>& height) {
    int len = height.size();
    int left = 0;
    int right = len - 1;
    int maxx = 0;
    while (left <= right)
    {
        int h = min(height[left], height[right]);
        int l = right - left;
        maxx = max(maxx,h * l);
        if (height[left] < height[right])
        {
            left++;
        }
        else
        {
            right--;
        }
    }
    return maxx;
}

int main()
{
    vector<int>height;
    for (int i = 0; i < 2; i++)
    {
        int a = 0;
        cin >> a;
        height.push_back(a);
    }
    int ans = maxArea(height);
    cout << ans;
    return 0;
}

I hope to share with you ！！！