计算调整塔形数组为连续升降序列所需最少砖块数（含代码问题）

问题描述 #

给定数组表示每座塔的砖块数量，需将塔调整为严格升序或严格降序序列（相邻元素高度差为1），且只能添加砖块（不能移除），计算所需的最少砖块数。

示例 #

• 示例1：
  输入数组：[1, 3, 5, 8]
  最优升序调整：[5, 6, 7, 8]
  所需砖块数：(5-1)+(6-3)+(7-5)+(8-8) = 9

• 示例2：
  输入数组：[3, 10, 9, 9, 4]
  最优降序调整：[12, 11, 10, 9, 8]
  所需砖块数：(12-3)+(11-10)+(10-9)+(9-9)+(8-4) = 15

原代码问题分析 #

原代码仅计算了一种固定递减序列的砖块添加量，既未考虑升序的可能，且该递减序列并非满足条件的最优序列。比如示例1中，原代码计算的是调整到[11,10,9,8]，添加量为21，远大于最优的9。

正确思路 #

需要分别计算升序、降序两种目标序列的最少添加量，再取最小值：

1. 升序序列：从右往左推导，保证每个位置的目标值 = 右侧目标值 -1，且不小于原数组对应位置的值，确保序列严格升序且添加砖块最少。
2. 降序序列：从右往左推导，保证每个位置的目标值 = 右侧目标值 +1，且不小于原数组对应位置的值，确保序列严格降序且添加砖块最少。

修正后的代码 #

def min_bricks(arr):
    n = len(arr)
    if n <= 1:
        return 0
    
    # 计算升序序列所需最少砖块（仅添加）
    ascending_target = [0] * n
    ascending_target[-1] = arr[-1]
    for i in range(n-2, -1, -1):
        ascending_target[i] = max(arr[i], ascending_target[i+1] - 1)
    ascending_cost = sum(t - a for t, a in zip(ascending_target, arr))
    
    # 计算降序序列所需最少砖块（仅添加）
    descending_target = [0] * n
    descending_target[-1] = arr[-1]
    for i in range(n-2, -1, -1):
        descending_target[i] = max(arr[i], descending_target[i+1] + 1)
    descending_cost = sum(t - a for t, a in zip(descending_target, arr))
    
    return min(ascending_cost, descending_cost)

# 测试示例1
arr1 = [1, 3, 5, 8]
print(min_bricks(arr1))  # 输出9

# 测试示例2
arr2 = [3, 10, 9, 9, 4]
print(min_bricks(arr2))  # 输出15

代码说明 #

• 升序序列推导：从最后一个元素开始（无需添加砖块），前面每个元素的目标值取「右侧元素目标值减1」和「原数组对应值」的最大值，既满足升序相邻差1的要求，又保证添加砖块最少。
• 降序序列推导：同样从最后一个元素开始，前面每个元素的目标值取「右侧元素目标值加1」和「原数组对应值」的最大值，满足降序相邻差1的要求。
• 最终返回两种序列添加量的最小值，即为最优解。

内容的提问来源于stack exchange，提问作者meallhour