C++面试宝典第16题:盛最多水的容器

2024-01-09 07:30:52

题目

        给定n个非负整数a1、a2、…、an,每个数代表坐标中的一个点(i, ai)。画n条垂直线,使得第i条垂直线的两个端点分别为(i, ai)和(i, 0)。找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水。说明:不能倾斜容器,且n的取值至少为2。

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

解析

        这道题主要考察应聘者将实际问题抽象化,并转化为数学模型的能力。

        我们最先想到的可能是“暴力法”,也就是遍历数组两遍。在第一遍遍历中,将数组中的元素(i, ai)和(i, 0)作为容器的左边界点。在第二遍遍历中,将数组中的元素(j, aj)和(j, 0)作为容器的右边界点。有了左边界点和右边界点,我们就可以计算出容器的容量。具体的实现,可以参考下面的示例代码。

#include <iostream>
using namespace std;

int GetMaxCapacity(int *pHeight, int nCount)
{
    int nMaxCapacity = 0;
    for (int i = 0; i < nCount - 1; i++)
    {
        for (int j = i 

文章来源:https://blog.csdn.net/hope_wisdom/article/details/135443432
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。