计算一维数组中的最大油轮体积 [英] 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屋!