Python程序：求解将子数组递增到目标数组所需的最小递增次数

假设我们有一个包含正值的数组 target。现在考虑一个大小相同的数组 initial，其所有值都为零。如果我们执行以下操作，我们需要找到从 initial 生成 target 数组所需的最小操作次数：（从 initial 中选择任何子数组并将每个值加一。）

因此，如果输入类似于 target = [2,3,4,3,2]，则输出将为 4，因为初始数组为 [0,0,0,0,0]。第一次选择从索引 0 到 4 的子数组并将其增加 1，因此数组将变为 [1,1,1,1,1]，然后再次选择从索引 0 到 4 的子数组使其变为 [2,2,2,2,2]，然后选择索引 1 到 3 的元素并递增，因此数组将变为 [2,3,3,3,2]，最后选择索引 2 并使数组变为 [2,3,4,3,2]，这与 target 相同。

为了解决这个问题，我们将遵循以下步骤：

  • prev_num := 0

  • steps := 0

  • 对于 target 中的每个 val，执行：

    • 如果 val > prev_num，则 steps := steps + val - prev_num；否则 steps := 0

    • prev_num := val

  • 返回 steps

示例

让我们看看下面的实现，以便更好地理解

def solve(target):
   prev_num = 0
   steps = 0
   for val in target:
      steps += val-prev_num if val > prev_num else 0
      prev_num = val
   return steps

target = [2,3,4,3,2]
print(solve(target))

输入

[2,3,4,3,2]

输出

4

更新于：2021年10月6日

249 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告