求将数组转换为bitonic数组所需最少操作数的高效算法

问题回顾 #

给定整数数组arr，每次操作可将任意元素减1，求转换为Bitonic数组的最少操作数。

• Bitonic数组定义：前缀/后缀可包含任意数量的0，非零部分需从1递增至某个峰值k，再递减至1（示例：[0,1,2,3,2,1,0,0]）

你提到的暴力解法时间复杂度为O(n² * M)（M为数组元素的最大值），当数组规模较大或元素值偏高时，运行效率极低，无法处理大规模输入。以下是高效的优化解法：

核心思路 #

通过预处理两个辅助成本数组，分别记录每个位置作为峰值时，左侧递增序列、右侧递减序列的最小操作成本，之后只需遍历所有可能的峰值位置和峰值大小，快速计算总操作数。

步骤1：预处理左侧成本数组 #

定义left_cost[i][k]为：将数组前i+1个元素（索引0到i）转换为以arr[i]为峰值k的递增序列（从1到k）所需的最少操作数。

为避免二维数组的高复杂度，我们维护前缀最小值数组min_left，其中min_left[k]表示到当前位置为止，选择不超过k的峰值的最小操作成本：

• 初始化min_left数组，大小为max_arr + 2，初始值为无穷大，min_left[0] = 0（峰值为0时左侧全0，操作数为0）
• 从左到右遍历每个元素arr[i]：
  1. 创建临时数组new_min_left，初始值为无穷大
  2. 对于每个可能的峰值k（1到arr[i]）：
     • 若i == 0，左侧无元素，成本为arr[i] - k
     • 否则，前一个位置的最大允许值为min(k-1, arr[i-1])，成本为min_left[min(k-1, arr[i-1])] + (arr[i] - k)
     • 将该成本存入new_min_left[k]
  3. 更新min_left为前缀最小值数组：min_left[k] = min(min_left[k-1], new_min_left[k])，确保后续能快速获取到不超过k的最小成本

步骤2：预处理右侧成本数组 #

类似左侧，定义right_cost[i][k]为：将数组从索引i到末尾的元素转换为以arr[i]为峰值k的递减序列（从k到1）所需的最少操作数。

维护前缀最小值数组min_right，从右到左遍历数组：

• 初始化min_right数组，大小为max_arr + 2，初始值为无穷大，min_right[0] = 0
• 从右到左遍历每个元素arr[i]：
  1. 创建临时数组new_min_right，初始值为无穷大
  2. 对于每个可能的峰值k（1到arr[i]）：
     • 若i == n-1，右侧无元素，成本为arr[i] - k
     • 否则，后一个位置的最大允许值为min(k-1, arr[i+1])，成本为min_right[min(k-1, arr[i+1])] + (arr[i] - k)
     • 将该成本存入new_min_right[k]
  3. 更新min_right为前缀最小值数组：min_right[k] = min(min_right[k-1], new_min_right[k])

步骤3：计算全局最小操作数 #

遍历每个位置i作为峰值位置，遍历所有可能的峰值k（1到arr[i]）：

• 总操作数 = left_cost[i][k] + right_cost[i][k] - (arr[i] - k)（减去重复计算的arr[i]-k，因为左右侧都统计了一次该值）
• 同时需考虑两种特殊情况：数组仅为递增序列（峰值在最后一位，后缀全0）、数组仅为递减序列（峰值在第一位，前缀全0），将这些情况的操作数也纳入对比

进一步优化：二分查找最优峰值 #

如果数组元素最大值M很大（如1e5），遍历所有k仍会有性能问题。此时可以对每个峰值位置i，通过二分查找找到使得总操作数最小的k值：

• 对于左侧，总操作数是关于k的先减后增的单峰函数
• 对于右侧同理，因此总操作数也是单峰函数，可通过二分查找快速定位最优k，将时间复杂度降至O(n log M)

示例验证 #

以示例1输入[3,3,3,3,3]为例：

• 峰值选在索引2，k=3时：
  • 左侧操作数：(3-1)+(3-2) = 2+1=3
  • 右侧操作数：(3-2)+(3-1)=1+2=3
  • 总操作数：3+3=6，与示例答案一致

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