求使数组非递减的最小拆分次数：算法缺陷与优化方向问询

需求说明 #

每次操作可将一个整数拆分为两个任意整数（拆分后数组长度+1），求将数组变为非递减序列所需的最小操作次数。
示例：数组[5, 2, 3]经两次拆分可变为[1, 2, 2, 2, 3]，最小操作次数为2。

现有实现的问题 #

以下是原实现代码：

def min_moves(x):
    moves = 0
    index = 2
    while index < len(x) + 1:
        if x[-index] > x[-index + 1]:
            moves += 1
            split1 = x[-index] // 2
            split2 = x[-index] - split1
            x = x[:-index] + [split1, split2] + x[-index + 1:]
 
        else:
            index += 1
        
    return moves

该算法在输入[2, 7, 3]时失效：原算法拆分后得到[2, 3, 4, 3]（不满足非递减），且未找到最优解（正确最优拆分应为[2, 2, 2, 3, 3]，操作次数为2）。核心问题在于实际修改数组的拆分方式逻辑粗糙，未考虑拆分后序列的整体非递减约束。

优化思路：贪心策略（无需实际拆分） #

核心逻辑为从后往前遍历，维护当前允许的最大后缀限制值，通过计算当前元素所需的最少拆分段数统计操作次数，无需修改原数组。

具体步骤 #

1. 初始化操作次数moves = 0，prev = x[-1]（最后一个元素无需拆分，作为初始限制值）。
2. 从倒数第二个元素开始向前遍历每个元素num：
   • 若num <= prev：直接更新prev = num，继续遍历（无需拆分）。
   • 若num > prev：
     • 计算最少拆分段数k：为保证拆分后的非递减序列最后一段不超过prev，且段数最少，k取ceil(num / prev)（每段最大为prev，总和为num，向上取整得到最少段数）。
     • 操作次数增加k - 1（拆分k-1次得到k段）。
     • 更新prev为num // k：拆分后的序列尽可能平均分配，让前面的元素更容易满足非递减要求。

优化后代码实现 #

import math

def min_moves(x):
    if len(x) <= 1:
        return 0
    moves = 0
    prev = x[-1]
    for num in reversed(x[:-1]):
        if num > prev:
            k = math.ceil(num / prev)
            moves += k - 1
            prev = num // k
        else:
            prev = num
    return moves

测试验证 #

• 输入[5,2,3]：返回2，与示例结果一致。
• 输入[2,7,3]：返回2，对应最优拆分后的非递减数组[2,2,2,3,3]。

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