復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

最大盛水量取決于兩邊中較短的那條邊，而且如果將較短的邊換為更短邊的話，盛水量只會(huì)變少。所以我們可以用兩個(gè)頭尾指針，計(jì)算出當(dāng)前最大的盛水量后，把邊往中間移，看能不能遇到更大的邊長(zhǎng)。只有更高的邊才可能有更大的面積。

• 如果是較高的邊往里面移，發(fā)現(xiàn)，無(wú)論邊變長(zhǎng)了還是短了，都不影響面積，因?yàn)檩^短邊是不會(huì)變的。而底還變小了，所以面積變小。 所以唯一的變大方法便是把較短邊往里移，看看能不能找到更高的。

注意

如果將較短的邊向中間移后，新的邊還更短一些，其實(shí)可以跳過(guò)，減少一些計(jì)算量

#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
#include <string>
#include <set>
using namespace std;

class Solution {
private:
    int min(int a, int b)
    {
        return a<b? a:b;
    }
    
    int max(int a, int b)
    {
        return a>b? a:b;
    }

public:
    int maxArea(vector<int>& height) {
        int size = (int)height.size();
        
        if (size <= 1) return 0;
        
        int left = 0, right = size - 1;
        
        int maxS = 0;
        
        while (left < right)
        {
            maxS = max(maxS, (right - left) * min(height[left], height[right]));
            
            if (height[left] < height[right])
            {
                int temp = left;
                
                while (temp < right && height[temp] <= height[left])
                    temp++;
                left = temp;
            }
            else
            {
                int temp = right;
                
                while (temp > left && height[temp] <= height[right])
                    temp--;
                right = temp;
            }
        }
        
        return maxS;
        
    }
};