LeetCode 补充题 189. 非降序数组的填充方案数
题目描述
牛客原题： ✅ 补充题 189. 非降序数组的填充方案数
数组中的
0表示被删除的数。将每个0填成1…k中的整数，使整个数组非降序，已有非零数不变。返回方案数模
1000000007。
示例 1：
输入：
nums = [1,0,0], k = 3
输出：6
解释： 后两个数可填为 (1,1)、(1,2)、(1,3)、(2,2)、(2,3)、(3,3)。
示例 2：
输入：
nums = [0,4,5], k = 6
输出：4
解释： 第一个位置可填 1、2、3、4，才能保持整个数组非降序。
提示：
-
0表示待填位置。 - 填入的值属于
1…k，已有非零值不能修改。 - 整个数组必须非降序。
- 答案对
1000000007取模。
题意分析
已有非零值不能改变，因此它们必须本身保持非降序；否则任何填法都无法修复。合法的已知值把所有零分成独立连续段，每段只受左右已知值以及填入范围
1～k约束。固定一个零段的可选值范围后，非降序要求让每种值的出现次数唯一决定排列，不应按逐位置任意选择来计数。用可重复组合计算每段方案数，再将独立段的结果相乘。
解法：按零段用可重复组合计数
核心思路
[!blue]
先按已有非零值把待填的零分段。某段两侧的已知值确定可填区间，再与
[1,k]取交集得到[low,high]；开头没有左邻、结尾没有右邻时，分别只受 1 和 k 限制。已有非零值若下降，填零无法修复。设一段有
m个零，可选值有V = high-low+1种。非降序要求决定了各值的排列顺序，所以只需决定每种值出现多少次，即求V个非负计数之和等于 m 的方案数。插板法得到C(V+m-1,m)。例如两个零可填 1 到 3 时，结果是11、12、13、22、23、33，共C(4,2)=6种。各零段的边界已经固定，选择互不影响，因此将段数相乘。代码用
count保存段长，previous保存左侧已知值；choose(high-low+count, count)对应上面的组合数。组合数的计算与分段思路分开讲：上界小于模数时，用分子乘积和分母逆元；上界跨过模数时，
choose按模数逐位拆分（Lucas），逐位计算并相乘。先解释为何要数非降序填法，再展开这部分数论实现。
解题步骤
- 顺序扫描非零值，若已有值出现下降则直接返回 0。
- 对中间、开头和结尾的每段零，把已知上下界与 [1,k] 相交。
- 非空零段范围为空则无解，否则乘上 C(high-low+count,count)。
- 用 Lucas 分解与快速幂逆元计算模组合数，跳过长度为零的段。
代码实现
class Solution {
private static final long MOD = 1_000_000_007;
private long power(long a, long n) {
long r = 1;
while (n > 0) {
if ((n & 1) != 0) {
r = r * a % MOD;
}
a = a * a % MOD;
n >>= 1;
}
return r;
}
private long choose(long n, long r) {
long answer = 1;
while (n > 0 || r > 0) {
long a = n % MOD;
long b = r % MOD;
if (b > a) {
return 0;
}
b = Math.min(b, a - b);
long up = 1;
long down = 1;
for (long i = 1; i <= b; i++) {
up = up * (a - b + i) % MOD;
down = down * i % MOD;
}
answer = answer * up % MOD * power(down, MOD - 2) % MOD;
n /= MOD;
r /= MOD;
}
return answer;
}
public int fillWays(int[] a, int k) {
long answer = 1;
long previous = Long.MIN_VALUE;
int start = 0;
for (int i = 0; i <= a.length; i++) {
if (i < a.length && a[i] == 0) {
continue;
}
if (i < a.length && a[i] < previous) {
return 0;
}
int count = i - start;
if (count > 0) {
long low = Math.max(1L, previous);
long high = i == a.length ? k : Math.min(k, a[i]);
if (low > high) {
return 0;
}
answer = answer * choose(high - low + count, count) % MOD;
}
if (i < a.length) {
previous = a[i];
}
start = i + 1;
}
return (int) answer;
}
}
func fillWays(a []int, k int) int {
const mod int64 = 1_000_000_007
power := func(a, n int64) int64 {
r := int64(1)
for n > 0 {
if n&1 != 0 {
r = r * a % mod
}
a = a * a % mod
n >>= 1
}
return r
}
choose := func(n, r int64) int64 {
answer := int64(1)
for n > 0 || r > 0 {
x, y := n%mod, r%mod
if y > x {
return 0
}
y = min(y, x-y)
up, down := int64(1), int64(1)
for i := int64(1); i <= y; i++ {
up = up * (x - y + i) % mod
down = down * i % mod
}
answer = answer * up % mod * power(down, mod-2) % mod
n /= mod
r /= mod
}
return answer
}
answer, previous, start := int64(1), int64(-1<<63), 0
for i := 0; i <= len(a); i++ {
if i < len(a) && a[i] == 0 {
continue
}
if i < len(a) && int64(a[i]) < previous {
return 0
}
count := i - start
if count > 0 {
low, high := max(int64(1), previous), int64(k)
if i < len(a) {
high = min(high, int64(a[i]))
}
if low > high {
return 0
}
answer = answer * choose(high-low+int64(count), int64(count)) % mod
}
if i < len(a) {
previous = int64(a[i])
}
start = i + 1
}
return int(answer)
}
复杂度分析
- 时间复杂度：总乘积循环不超过零元素数量；含模幂时，时间 $O(n \log P)$，P=1000000007。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
已知值把零段分开后，各段选择互不影响；每段用每种值的出现次数唯一表示非降序填法，所以是可重复组合而不是排列。
易错点总结
[!yellow]
- 只有填入值受 [1,k] 限制，已有非零值保持不变；例如 [5]、k=3 没有零且已非降序，答案为 1。
- 相邻已知值逆序时无解；非空零段的上下界与 [1,k] 取交集后为空也无解。
- 零段内部必须非降序，不能按 V 的 m 次方计数。
- 组合数上界可能跨越 P，直接对含 P 因子的分母取逆元会错，需先按 Lucas 分解。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 62. 不同路径 | 中等 | 非降序选数可转为隔板法，与网格路径一样归结为组合数。 |