LeetCode Hot100(5.盛最多水的容器）

5.盛最多水的容器题目给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明你不能倾斜容器。示例 1输入[1,8,6,2,5,4,8,3,7]输出49解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。示例 2输入height [1,1]输出1解法一暴力遍历代码class Solution { public: int maxArea(vectorint height) { int max_area0; for(int i0;iheight.size();i){ for(int ji1;jheight.size();j){ max_area max(max_area,min(height[i],height[j])*(j-i)); } } return max_area; } };但是方法一的时间复杂度太大了为On²解法二双指针代码class Solution { public: int maxArea(vectorint height) { int left0,rightheight.size()-1; int max_area (right-left)*min(height[right],height[left]); while(leftright){ if(height[left]height[right]){ left; } else{right--;} max_area max(max_area,(right-left)*min(height[right],height[left])); } return max_area; } };