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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。