如何高效统计符合条件的山脉数组（Mountain Array）数量？

问题分析 #

给定奇数长度A和数字范围[1,B]，统计符合以下特征的山脉数组数量：

• 所有元素互不相同
• 前(A-1)/2个元素严格递增，后(A-1)/2个元素严格递减
• 中间元素是数组最大值

暴力枚举所有排列的时间复杂度为O(B!/(B-A)!)，当B和A较大时完全不可行，我们可以通过数学推导得到高效解法。

数学推导 #

1. 选元素集合：首先从B个元素中选A个不同的元素，共有C(B,A)种选法（组合数）。
2. 排列元素：对于每个选出的元素集合，最大值固定在中间位置。剩下的A-1个元素需要分成左右各k=(A-1)/2个元素：
   • 从A-1个元素中选k个放在左侧，剩下的放右侧，共有C(A-1,k)种分配方式。
   • 左侧元素必须严格递增，只有1种排列方式（从小到大）；右侧元素必须严格递减，也只有1种排列方式（从大到小）。

因此，总数量为两个组合数的乘积：
总数 = C(B,A) * C(A-1, (A-1)/2) mod 10^9

代码实现 #

使用Java实现，通过BigInteger处理组合数的精确计算，避免溢出问题：

public class MountainArrayCount {
    private static final int MOD = 1000000000;

    // 计算组合数C(n,k)，返回模1e9的结果
    public static long comb(long n, long k) {
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1;
        k = Math.min(k, n - k); // 优化计算次数，取较小的k值
        BigInteger result = BigInteger.ONE;
        for (int i = 1; i <= k; i++) {
            result = result.multiply(BigInteger.valueOf(n - k + i))
                           .divide(BigInteger.valueOf(i));
        }
        return result.mod(BigInteger.valueOf(MOD)).longValue();
    }

    public static long countMountainArrays(int A, int B) {
        if (A > B) return 0; // 无法选出A个不同元素，直接返回0
        int k = (A - 1) / 2;
        long c1 = comb(B, A);
        long c2 = comb(A - 1, k);
        return (c1 * c2) % MOD;
    }

    public static void main(String[] args) {
        // 测试示例：A=3，B=4，预期输出8
        System.out.println(countMountainArrays(3, 4));
    }
}

复杂度分析 #

• 计算组合数C(n,k)的时间复杂度为O(min(k, n-k))，因此整体时间复杂度为O(A)，远优于暴力枚举的阶乘级复杂度。

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