復(fù)雜度
時間 O(N) 空間 O(N)
思路
最大盛水量取決于兩邊中較短的那條邊躬它，而且如果將較短的邊換為更短邊的話顷牌，盛水量只會變少沟优。所以我們可以用兩個頭尾指針岔擂，計算出當(dāng)前最大的盛水量后赛不，把邊往中間移惩嘉，看能不能遇到更大的邊長。只有更高的邊才可能有更大的面積踢故。
- 如果是較高的邊往里面移文黎，發(fā)現(xiàn)，無論邊變長了還是短了殿较，都不影響面積耸峭，因為較短邊是不會變的。而底還變小了淋纲，所以面積變小劳闹。 所以唯一的變大方法便是把較短邊往里移，看看能不能找到更高的洽瞬。
注意
如果將較短的邊向中間移后本涕，新的邊還更短一些，其實(shí)可以跳過伙窃，減少一些計算量
#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;
}
};
