时间戳

首页 > 解决方案 > 最小化数组的“成本”

algorithm - 最小化数组的“成本”

问题描述

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

  • 如果 i < k 则成本=max{A[i], A[i+1],...,A[k]}
  • 如果 i = k 则成本 = A[k]
  • 如果 i > k 则成本=max{A[k], A[k+1],...,A[i]}

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

例如 A = 3, 3, 2, 5, 1, 4, 3
k=2 (A[2]=2) 的最小成本是 28

  • 最大{A[0], A[1], A[2]}=3
  • 最大{A[1], A[2]}=3
  • A[2]=2
  • 最大{A[2], A[3]}=5
  • 最大{A[2], A[3], A[4]}=5
  • 最大{A[2], A[3], A[4], A[5]}=5
  • 最大{A[2], A[3], A[4], A[5], A[6]}=5

成本=3+3+2+5+5+5+5=28

标签： algorithm

解决方案

这可以在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]成为 所有人f(j, k)的j总和[0, 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]}]

请注意，此序列是非递增的。因此，我们可以用单调递减的 stack对我们得到的总和进行建模。让我们看看如何：

当我们从 到 的总和进行转换时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))

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

推荐阅读