leetcode11.盛最多水的容器-白红宇的个人博客

leetcode11.盛最多水的容器

发布日期：2021-05-15 09:03:37 浏览次数：18 分类：精选文章

本文共 500 字，大约阅读时间需要 1 分钟。

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

这个问题可以通过双指针方法来解决。具体步骤如下：

初始化两个指针left和right，分别从数组的开头和结尾开始。

计算当前两指针之间的水平距离b。

比较height[left]和height[right]的高度。

如果height[left]小于等于height[right]，则取height[left]作为容器的高度，并将left指针向右移动一位。

否则，取height[right]作为容器的高度，并将right指针向左移动一位。

计算当前水平距离b与容器高度h的乘积，作为当前的水容量。

比较当前容量与最大容量res，更新最大容量。

重复步骤2至7，直到left指针超过right指针。

这种方法的时间复杂度为O(n)，因为每个指针最多移动n次。该算法能够高效地解决问题，并且实现简单易懂。

通过上述方法，可以轻松找到能够容纳最多水的两条垂直线与x轴围成的区域。

上一篇：leetcode12.整数转罗马数字

下一篇：leetcode9.回文数

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！