【LeetCode】11. Container with the most water

The easiest way to think of is to set two pointers to traverse all the cases in turn , Then find the biggest one , But the time complexity of this method is O(n²), The result of the last run will time out , So a better way is needed .

Ideas ： Two pointers at the beginning, one to the beginning and one to the end , At this time, the bottom of the container is the largest , Next, as the pointer moves inward , It will make the bottom of the container smaller , In this case, you want to make the container contain more water , It's just about the height of the container . So how do we decide which pointer to move ？ We can find that whether the left pointer moves one bit to the right , Or the right pointer moves one bit to the left , The bottom of the container is the same , Are less than before 1. In this case, we want to increase the area of the container after the pointer is moved , Make the height of the moved container as large as possible , So we choose the pointer with the lower height to move , So we keep the higher side of the container , Give up the smaller side , To get a chance to have a higher edge .

class Solution {
    
public:
    int maxArea(vector<int>& height) {
    
        int maximum = 0;
        int low = 0, high = height.size() - 1;
        while(low < high){
    
            int h = min(height[low], height[high]);
            maximum = max(maximum, h * (high - low));
            if(height[low] < height[high]) low++;  // The one with small moving height 
            else high--;
        }
        return maximum;
    }
};