时间戳

首页 > 解决方案 > 装水最多的容器

javascript - 装水最多的容器

问题描述

我正在通过 geeksforgeeks 上的以下问题

给定 n 个非负整数 a_1, a_2, ..., a_n，其中每个表示坐标 (i, a_i) 处的一个点。绘制“n”条垂直线，使线 i 的两个端点位于 (i, a_i) 和 (i, 0)。找到两条线，它们与 x 轴一起形成一个容器，使得容器中的水最多。

程序应该返回一个整数，它对应于可以容纳的最大水面积（最大面积而不是最大体积听起来很奇怪，但为了简单起见，这是我们正在使用的 2D 平面）。

问题链接：https ://www.geeksforgeeks.org/container-with-most-water/

在这里，他们给出了以下示例并进行了解释

Input : [1, 5, 4, 3]
Output : 6
Explanation : 
5 and 3 are distance 2 apart. 
So the size of the base = 2. 
Height of container = min(5, 3) = 3. 
So total area = 3 * 2 = 6

Input : [3, 1, 2, 4, 5]
Output : 12
Explanation : 
5 and 3 are distance 4 apart. 
So the size of the base = 4. 
Height of container = min(5, 3) = 3. 
So total area = 4 * 3 = 12

但我仍然无法弄清楚问题需要我做什么？比如为什么在第一个示例中他们选择了第二个和最后一个元素（5 和 3），而在第二个示例中他们选择了第一个和最后一个元素？

标签： javascript

解决方案

您必须确定输入中的哪两行，当它们一起时，创建的容器中水最多。

对于第一个示例，使用1, 5, 4, 3，您的其他一些选项是：

  • 1 和 5：结果是面积 1（1 分开 * 1 分钟高度）

  • 1 和 4：结果是面积 2（2 分开 * 1 分钟高度）

  • 1 和 3：结果是面积 3（3 分开 * 1 分钟高度）

  • 5 和 4：结果是面积为 4（1 分开 * 4 分钟高度）

  • 4 和 3：结果是面积为 3（1 分开 * 1 分钟高度）

将 5 和 3 放在一起（相隔 2；索引 1 和索引 3）是理想的结果，因为它会产生最高区域 (3 * 2 = 6)。

对于第二个示例，您的其他一些选项是：

  • 3 和 1：结果是面积 1（1 间隔 * 1 分钟高度）

  • 3 和 2：结果是面积 4（2 分开 * 2 分钟高度）

  • 3 和 4：结果是面积为 9（3 分开 * 3 分钟高度）

等等。最高的结果是 3 和 5（相隔 4；索引 0 和索引 4），其面积为 12 (3 * 4)。

推荐阅读