计算一维数组中的最大油轮体积 [英] Calculate largest tanker volume in one dimensional array

问题描述

我有以下困惑:创建一种方法来计算将用于容纳洪水的最大油轮容积.方法输入:一维整数数组和一个表示加油机宽度的整数值.

I have the following puzzle: Create a method to calculate the largest tanker volume that will be used to hold floodwater. Method input: a one-dimensional array of integers and one integer value that represents the width of the tanker.

integer getLargestTanker(Integer width, Integer[] values)

一维数组包含表示油轮高度的整数值.数组中这些整数值之间的距离表示油轮长度.

The one-dimensional array contains integer values that represent the tanker heights. The distance between those integer values in the array represents the tanker length.

假设我们有以下数组: {2，9，6，6，3，5，7} 我们需要选择两个数字，以使有效高度和长度(这两个数字之间的距离)的乘积最大.如果我们选择2和9，则有效的油轮高度为:2且距离为1.在此示例中，最大油轮体积值为7x4x(静态给定宽度).因为我们应该选择高度:9和7.说明:有效高度为7(因为它是一个装水的油轮).油轮的长度为4(索引1和索引7).

Let's say we have the following array: {2, 9, 6, 3, 5, 7} We need to pick two numbers such that the product of the effective height and length (distance between those two numbers) is the maximum. If we pick 2 and 9, the effective tanker height is: 2 and the distance is 1. In this example, the maximum tanker volume value would be 7x4x(static given width). Because we should choose heights: 9 and 7. Explanation: the effective height is 7 (since it's a tanker that holds water). The length of the tanker is 4 (index-1 and index-7).

两个嵌套循环.复杂度为O(n ^ 2).我坚信应该有一个更好的解决方案，但是我无法提出一个解决方案.你有更好的主意吗?

Two nested loops. Complexity is O(n^2). I strongly believe that there should be a better solution, but I couldn't come up with one. Do you have any better idea?

推荐答案

配对两个高度时，体积由最小高度决定.

When pairing two heights, the volume is determined by the minimum height.

然后，我们将重点放在确定这对鞋的最小身高上.对于对应于高度 A [i] 的每个索引 i ，我们确定对应的最小和最大索引所有大于 A [i] 的 A 值.

Then, we focus here on the determination of the min height of this pair. For each index i, corresponding to a height A[i], we determine the minimum and the maximum indices corresponding to all A values greater than A[i].

为此，我们根据值 A [i] 对索引 i = index [.] 进行排序.对于给定的 i = index [j] ，对于 k> ;，所有候选索引都对应于 index [k] .我.

For that, we sort the indices i = index[.] according to the values A[i]. For a given i = index[j], all canditate indices correspond to the index[k], for k > i.

一个简单的循环允许查找这些 index [k] 的最小值和最大值.

A simple loop allow to find the minimum and maximum values of these index[k].

复杂度取决于排序:O(nlogn)

The complexity is dominated by the sorting: O(nlogn)

这是C ++中的代码，无论您使用哪种语言，都非常简单易懂.

Here is a code in C++, rather simple and easy to understand whatever the language you are using.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int max_vol (const std::vector<int> &A) {
    int vmax = 0;
    int n = A.size();
    std::vector<int> index(n);
    std::iota (index.begin(), index.end(), 0);
    auto comp = [&] (int i, int j) {return A[i] < A[j];};
    std::sort (index.begin(), index.end(), comp);
    int index_max = index[n-1];
    int index_min = index[n-1];
    for (int i = n-2; i >= 0; --i) {
        int d0 = std::abs (index[i] - index_max);
        int d1 = std::abs (index[i] - index_min);
        int vol = std::max (d0, d1) * A[index[i]];
        if (vol > vmax) vmax = vol;
        index_max = std::max(index[i], index_max);
        index_min = std::min(index[i], index_min);      
    }
    return vmax;
}

int main() {
    std::vector<int> heights = {2, 9, 6, 3, 5, 7};
    auto max_volume = max_vol (heights);
    std::cout << "max volume = " << max_volume << std::endl;
}

这篇关于计算一维数组中的最大油轮体积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！