填充数组0值并保持非递减顺序的算法求解问题

问题说明 #

给定包含0值的整数数组（例如[0,2,3]、[1,0,0]），其中0代表需要填充的缺失值，需满足以下规则：

• 给定正整数k，所有填充的数值范围为1到k（包含边界）
• 填充完成后数组需满足a₁<=a₂<=a₃…<=aₙ的非递减顺序，不可调整原有非0元素的索引位置，不可对数组整体排序

原有代码仅能处理数组中仅有1个0的场景，核心问题是没有覆盖多个0的组合填充逻辑，也没有提前做约束剪枝，存在大量无效判断。

可行实现思路 #

采用回溯法处理所有0的位置，每次填充当前0值时，直接通过前后约束限定取值范围，避免无效遍历：

1. 先定位数组中所有0的位置
2. 填充第i个0时，取值下限为前一个位置的数值（如果是数组首个元素则下限为1）
3. 填充第i个0时，取值上限为后一个最近的非0数值（如果后面没有非0值则上限为k）
4. 所有0填充完成后直接加入结果集，无需再次校验非递减属性（因为填充时已经满足约束）

代码实现 #

def fill_zero_array(arr, k):
    res = []
    zero_pos = [i for i, num in enumerate(arr) if num == 0]
    n = len(arr)
    
    def backtrack(index):
        # 所有0已经填充完成
        if index == len(zero_pos):
            res.append(arr.copy())
            return
        cur_pos = zero_pos[index]
        # 确定当前填充值的下限
        low = 1 if cur_pos == 0 else arr[cur_pos - 1]
        # 确定当前填充值的上限
        high = k
        for i in range(cur_pos + 1, n):
            if arr[i] != 0:
                high = arr[i]
                break
        # 遍历所有合法取值递归
        for val in range(low, high + 1):
            arr[cur_pos] = val
            backtrack(index + 1)
            # 回溯撤销赋值
            arr[cur_pos] = 0
    
    backtrack(0)
    return res

# 测试用例1
k1 = 3
a1 = [0,2,3]
print(fill_zero_array(a1, k1)) # 输出 [[1,2,3], [2,2,3]]

# 测试用例2
k2 = 3
a2 = [1,0,0]
print(fill_zero_array(a2, k2)) # 输出 [[1,1,1], [1,1,2], [1,1,3], [1,2,2], [1,2,3], [1,3,3]]

内容的提问来源于stack exchange，提问作者Song Calderone Zhang