题解 | #填充数组#

import java.util.*;
public class Solution {
    public int FillArray (int[] a, int k) {
        long ans = 1;
        int n = a.length;
        //横坐标是数组的长度，纵坐标是最大的值
        long[][] dp = new long[n+1][k+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                if(i == 1){
                    //只有一个空格的话，最大为j,那么一定有j中填充方法
                    dp[i][j] = j;
                }else{
                    //dp[i][j-1]实际上就对应这dp[i-1][0]~dp[i-1][j-1]的和
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
                }
            }
        }
        //例子  a:2 0 0 4 5 k:6
        for(int i = 0; i < a.length;i++){
            if(a[i] == 0){
                //终于遇见了一个0（空格）
                int p = i;//标记一下这一段第一个出现的空格 p = 1
                //统计一下这一段出现了多少的空格
                while(i < a.length && a[i] == 0) 
                    i++;//出现了2个
                //此时i为3
                //down和up决定了这2个空格的取值范围
                int down = (p == 0) ? 1 : a[p-1];
                //如果p为0说明数组的第一个元素就是0，取值下限就是1,
                //如果p非0，下限就是本轮中第一次出现0的前一个元素的值即a[p-1](2)
                int up = (i == a.length) ? k : a[i];
                //如果本段中的i为a数组的长度，上限就是题目规定的k的大小
                //如果不是，上限就是此时a[i](4)
                int opportunity = up - down + 1;
                //总的取值范围为4-2+1 = 3 可以取2 3 4 这三个值
                int len = i - p;
                //0的个数是i-p(3-1=2)
                ans = (ans * dp[len][opportunity]) % 1000000007;
                //每段算出来的结果是需要相乘的
                //此时的i下标为3的地方（其值必不为0，回到循环后直接++跳过）
            }
        }
        //返回的值也一定要进行取模操作
        return (int)(ans % 1000000007);
    }
}