11-盛最多水的容器

@Author:CSU张扬
@Email:csuzhangyang@gmail.com or csuzhangyang@qq.com

1. 题目

给定 n n n 个非负整数 a 1 , a 2 , . . . , a n a1,a2,...,an a1a2...an,每个数代表坐标中的一个点 ( i , a i ) (i, ai) (i,ai) 。在坐标内画 n n n 条垂直线,垂直线 i i i 的两个端点分别为 ( i , a i ) (i, ai) (i,ai) ( i , 0 ) (i, 0) (i,0)。找出其中的两条线,使得它们与 x x x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n n n 的值至少为 2。
在这里插入图片描述
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49

示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/container-with-most-water/

2. 解法

2.1 解法一:双指针法

参考:Krahets

  1. 指针 l l l r r r 分别指向最左边和最右边的木板,根据规则移动两个指针。获取每次移动之后的容器的大小,最后得到一个最大值。
  2. 由题意可知, S = 底 × 高 = ( r − l ) × m i n ( h [ l ] , h [ r ] ) S = 底\times高 = (r - l) \times min(h[l], h[r]) S=×=(rl)×min(h[l],h[r]),面积是由两个木板中的短板决定的。
  3. 无论我们移动哪一侧的木板,底 ( r − l ) (r - l) (rl) 都会减1。
    1. 如果我们选择短板一侧的指针向内移一格,那么容器的宽 m i n ( h [ l ] , h [ r ] ) min(h[l], h[r]) min(h[l],h[r]) 可能变小也可能变大
    2. 如果我们选择长板一侧的指针向内移一格,那么容器的宽 m i n ( h [ l ] , h [ r ] ) min(h[l], h[r]) min(h[l],h[r]) 可能不变也可能变小
  4. 所以,我们可以推断出,只有向内移动短板一侧的指针, S S S 才可能会变大(虽然也可能变小)。但是向内移动长板一侧的指针, S S S 一定不会变大

执行用时: 16 ms, 在所有 cpp 提交中击败了95.90%的用户
内存消耗: 9.8 MB, 在所有 cpp 提交中击败了75.70%的用户

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

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐