LeetCode 11. 盛最多水的容器


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

说明:你不能倾斜容器。

示例

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

思路

做法:用两个指针 i,j 分别指向首尾,如果 $a_i>a_j$,则 j−−;否则 i++,直到 i=j 为止,每次迭代更新最大值。

证明:假设最优解对应的两条线的下标是 i′,j′(i′<j′),在 i,j 不断靠近的过程中,不妨假设 i 先走到 i′,则此时有 j′<j。反证,如果此时 $a_i≤a_j$,设 S 表示 i,j能盛多少水i,j能盛多少水,S′ 表示 i′,j′ 能盛多少水,则:
$S=min(ai,aj)∗(j−i)$
$=a_i∗(j−i)$
$>a_i∗(j′−i)>a_i∗(j′−i)$
$≥min(a_i,a_j′)∗(j′−i)=S′≥min(a_i,a_j′)∗(j′−i)=S′$
与 S′ 是最优解矛盾,因此 $a_i>a_j$,所以 j 会一直走到 j′,从而得到最优解。

来源AcWing@yxc

时间复杂度

$O(n)$

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        for (int i = 0, j = height.size() - 1; i < j; )
        {
            res = max(res, min(height[j], height[i]) * (j - i));
            if (height[i] < height[j]) i++;
            else j--;
        }
        return res;
    }
};
百度已收录
  • 分享:
评论
还没有评论
    发表评论 说点什么