最小化数组的“成本”

Question

假设我有一个大小为N的数组A，如果我选择一个数字k，0 <= k< N，元素Ai的成本定义为：

• 如果我
• ，如果我=k，那么cost=Ak
• ，如果我>k，那么cost=max{Ak，Ak+1，.，Ai}

我需要找到使成本和最小成本最小化的k。

例如，A= 3，3，2，5，1，4，3

k=2 (A2=2)的最低成本为28

{A，A1，A2}=3

• max{A1，A2}=3

• A2=2

• max{A2，A3}=5

• max{A2，A3，A4}=5

• max{A2，A3，A4，A5}=5

• max{A2，A3，A4，A5，A6}=5

cost=3+3+2+5+5+5+5=28

Answer 1

这可以在O(N)中解决。让我们分析一下这个问题。

我们注意到的第一件事是，对于给定的k，它的左侧和右侧是独立的。我们可以把它分解成三个部分：left[k]，它是所有i <= k的最大和，right[k]是所有i >= k的最大和，以及arr[k]。在这种情况下，cost(k) = left[k] + right[k] - arr[k]。注意，arr[k]在left中被计算过一次，在right中又被计算了一次，所以我们必须在最后减去它。

我们只需要了解如何有效地计算left和right。

一些正式定义：

让f(i, k)是max{A[i], A[i+1], ..., A[k]}，left[k]是[0, k]上所有j的所有f(j, k)之和。

让我们考虑总结为left[k]的每个元素。我们有一个类似于下面的序列，其中left[k] = sum(sums)。

sums = [max{A[0], A[1], ..., A[k]}, max{A[1], A[2], ..., A[k]}, ...,max{A[k]}]

注意，这个序列是不增加的。因此，我们可以用单调递减的叠加来建模我们得到的和。让我们看看如何：

当我们从left[i]和转换到left[i + 1]时，我们在和中添加A[i + 1]，然后将和中的每个元素设置为小于A[i + 1]到A[i + 1]的元素。一旦我们将该元素设置为A[i + 1]，它的原始值就不再重要了。

我们可以利用这样的机会。让stack[i]是表单(value, multiplicity)中的一个元组。我们让堆栈表示和的每个组成部分，这样

left[i] = sum(value * multiplicity for value, multiplicity in stack)。请注意，这也等于前面的sum(sums)。

下面是在添加元素时更新堆栈的方法：

stack = []
for element in A:
    element_count = 1
    # while the previous element is less than this one
    # we merge it into this one
    while stack and stack[-1][0] <= element:
        element_count += stack.pop()[1]
    stack.append((element, element_count))

注意，完成的总工作量是O(N)，每个元素每增加一次并从堆栈中移除一次，因此有O(2N) = O(N)工作完成。

要计算left[i]，我们可以在每次迭代时取sum(value * multiplicity for value, multiplicity in stack)，但这非常慢。相反，我们可以在从堆栈中添加和删除元素时维护运行的和：

stack = []
left = []
running_sum = 0

for element in A:
    element_count = 1

    while stack and stack[-1][0] <= element:
        v, mul = stack.pop()
        element_count += mul
        running_sum -= v * mul
    running_sum += element * element_count
    left.append(running_sum)
    stack.append((element, element_count))

我们刚刚在O(N)中计算了O(N)！我们也可以在数组的反面使用相同的策略来计算right中的O(N)。一旦我们有了left和right，我们就可以在O(1)中计算cost(k)，这样就可以在O(N)中找到最大的k。