leetcode11. 盛最多水的容器，双指针法

leetcode11. 盛最多水的容器

给定一个长度为 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

题目分析

我们需要找到能够容纳最多水的两根柱子，并返回它们所能容纳的水量。我们可以使用双指针方法，从数组的两端开始向中间移动，每次移动较短的柱子，计算当前柱子所能容纳的水量，并更新最大水量。

总体思维导图

• 寻找最多水的两根柱子
• 使用双指针方法
• 从数组的两端开始向中间移动
• 每次移动较短的柱子
• 计算当前柱子所能容纳的水量
• 更新最大水量

算法步骤

1. 初始化左右指针 l 和 r，分别指向数组的两端。
2. 当 l<r 时，执行以下步骤：
   • 计算当前柱子所能容纳的水量 temp=min(height[l],height[r])*(r-l)。
   • 更新最大水量 res=max(res,temp)。
   • 如果 height[l]<=height[r]，则 l++；否则 r–。
3. 返回最大水量 res。

具体代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res=INT_MIN;
        int l=0;
        int r=height.size()-1;
        while(l<r)
        {
        int temp=min(height[l],height[r])*(r-l);
        res=max(res,temp);
        if(height[l]<=height[r]) l++;
        else r--;
        }
        return res;
    }
};

func maxArea(height []int) int {
    l:=0
    r:=len(height)-1
    res:=0
    for ;l<r;{
        temp:=min(height[l],height[r])
        res=max(res,temp*(r-l))
        if(height[l]<=height[r]){
            l++
        }else{
            r--
        }
    }
    return res
}

算法流程图

算法分析

• 时间复杂度：O(n)，其中 n 是数组的长度。
• 空间复杂度：O(1)。
• 易错点：在更新左右指针时，需要根据当前柱子的高度来决定移动哪个指针。
• 注意事项：在计算当前柱子所能容纳的水量时，需要使用 min(height[l],height[r])*(r-l) 来计算。

相似题目