相关疑难解决方法(0)

给定一个数组,为每个元素找到数组中的下一个较小元素,而不改变元素的原始顺序.

例如,假设给定的数组是4,2,1,5,3.

结果数组为2,1,-1,3,-1.

我在接受采访时被问到这个问题,但我想不出一个比普通的O(n ^ 2)解决方案更好的解决方案.我能想到的任何方法,即制作二元搜索树,或对数组进行排序,都会扭曲元素的原始顺序,从而导致错误的结果.

任何帮助将受到高度赞赏.

我有一个数字数组，现在我必须通过生成给定数组的所有可能的子数组并应用一些条件来查找元素之和。

条件是对每个子数组获取minimum并在其中找到total of elements并将两者相乘(minimum * total)。最后，add所有子数组的所有这些相乘值。

这是问题陈述：

使用以下公式查找所有可能子数组的总和：

\n

Sum(left, right) = (min of arr[i]) * (\xe2\x88\x91 arr[i])，其中 i 的范围从左到右。

\n

例子：

Array = [2,3,2,1]\n

子数组是：[start_index, end_index]

 [0,0] subarray = [2], min is 2 and total of items = 2. min * total = 2*2=4\n [0,1] subarray = [2,3], min is 2 and total of items = 5. min * total = 2*5=10\n [0,2] …

假设数组是A={1,2,3}，现在获取该数组的所有子数组。对于每个子数组，找到该子数组中的最小值，并找到该子数组中的项目之和。最后添加所有这些值。输入无法排序，因为我想要所有可能的子数组。

例子：

可能的子数组是：

{1} - min = 1, sum = 1 => min* sum = 1
{1,2} - min = 1, sum = 3 => min* sum = 3
{1,2,3} - min = 1, sum = 6 => min* sum = 6
{2} - min = 2, sum = 2 => min* sum = 4
{2,3} - min = 2, sum = 5 => min* sum = 10
{3} - min = 3, sum = 3 => min* …

给定一个数组，我应该在线性时间内计算以下总和：

我最幼稚的实现是 O(n ³ )：

sum_ = 0

for i in range(n):
    for j in range(n, i, -1):
        sum_ += max(arr[i:j]) * (j-i)

我不知道该怎么做。我尝试过很多算法，但它们最多是 O(n*log(n))，但我应该在线性时间内解决它。另外，我不明白，是否有一种数学方法可以只查看数组并告诉上面总和的结果？