【LeetCode-数组】称最多水的容器

题目描述

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

题目链接：https://leetcode-cn.com/problems/container-with-most-water/

思路1

暴力求解。使用两层循环求面积并记录当前的最大值，代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int area = 0;
        for(int i=0; i<height.size(); i++){
            for(int j=0; j<height.size(); j++){
                if(i!=j){
                    int w = i-j<0? j-i:i-j;
                    int h = height[i]>height[j]? height[j]:height[i];
                    area = area>w*h? area:w*h;
                }
            }
        }
        return area;
    }
};

• 时间复杂度：O(n^2)
  两层遍历，由于时间复杂度过高，这种方法没有通过。
• 空间复杂度：O(1)

思路2

双指针法。两条垂直线围成的面积取决于两条垂直线之间的距离以及较短的那条垂直线的长度。首先，使用两个指针left、right分别指向第一条垂直线和最后一条垂直线使得距离最大，然后移动较短的那条垂直线，因为移动较短的那条线可能会遇到更长的线，虽然两条线之间的距离变短了，但是由于短的那条垂直线的长度增加了，所以还有有可能获得更大的面积的。重复这个过程直至left>=right。代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size()<2){
            return 0;
        }

        int maxarea = -1;
        int left = 0;
        int right = height.size()-1;
        while(left<right){
            int area = (right-left)*min(height[left], height[right]);
            maxarea = max(area, maxarea);
            if(height[left]<height[right]){
                left++;
            }else{
                right--;
            }
        }
        return maxarea;
    }
};

• 时间复杂度：O(n)
  遍历一遍数组，所以时间复杂度为O(n)
• 空间复杂度：O(1)