算法-盛最多水的容器

题目:

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

    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function maxArea($arr) {
        $count = count($arr);
        $l = 0;
        $r = $count - 1;
        $res = 0;
        while ($l < $r) {
            $h = min($arr[$l],$arr[$r]);
            $res = max($res,$h * ($r-$l));
            if ($arr[$l] < $arr[$r]) {
                $l ++ ;
            } else {
                $r --;
            }
        }
        return $res;
    }
}

M先生博客
请先登录后发表评论
  • latest comments
  • 总共0条评论