题目

给你一个长度为 n 的数组 complexity。

在房间里有 n 台 上锁的 计算机，这些计算机的编号为 0 到 n - 1，每台计算机都有一个 唯一 的密码。编号为 i 的计算机的密码复杂度为 complexity[i]。

编号为 0 的计算机密码已经 解锁 ，并作为根节点。其他所有计算机必须通过它或其他已经解锁的计算机来解锁，具体规则如下：

• 可以使用编号为 j 的计算机的密码解锁编号为 i 的计算机，其中 j 是任何小于 i 的整数，且满足 complexity[j] < complexity[i]（即 j < i 并且 complexity[j] < complexity[i]）。
• 要解锁编号为 i 的计算机，你需要事先解锁一个编号为 j 的计算机，满足 j < i 并且 complexity[j] < complexity[i]。

求共有多少种 [0, 1, 2, ..., (n - 1)] 的排列方式，能够表示从编号为 0 的计算机（唯一初始解锁的计算机）开始解锁所有计算机的有效顺序。

由于答案可能很大，返回结果需要对 109 + 7 取余数。

注意：编号为 0 的计算机的密码已解锁，而 不是 排列中第一个位置的计算机密码已解锁。

排列 是一个数组中所有元素的重新排列。

示例 1：

输入： complexity = [1,2,3]

输出： 2

解释：

有效的排列有：

• [0, 1, 2]
  • 首先使用根密码解锁计算机 0。
  • 使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。
  • 使用计算机 1 的密码解锁计算机 2，因为 complexity[1] < complexity[2]。
• [0, 2, 1]
  • 首先使用根密码解锁计算机 0。
  • 使用计算机 0 的密码解锁计算机 2，因为 complexity[0] < complexity[2]。
  • 使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。

示例 2：

输入： complexity = [3,3,3,4,4,4]

输出： 0

解释：

没有任何排列能够解锁所有计算机。

提示：

• 2 <= complexity.length <= 10^5
• 1 <= complexity[i] <= 10^9

解题思路

这道题的关键在于分析 计算机 0 (根节点) 的特殊地位。

1. 题目规则分析

• 初始状态：只有计算机 0 是解锁的。
• 解锁条件：要解锁计算机 $i$，必须先解锁一个计算机 $j$，满足两个条件：
  1. $j < i$ （索引更小）
  2. $complexity[j] < complexity[i]$ （复杂度更低）

2. 关键推导：必须存在一条“递增链”

为了解锁任意一台计算机 $i$，我们需要一条从初始解锁节点（计算机 0）开始的解锁链：

$0 \rightarrow \dots \rightarrow j \rightarrow i$

在这个链条中，每一步的复杂度必须是 严格递增 的。

这意味着，能够被解锁的任意计算机 $i$，其复杂度 $complexity[i]$ 必须 严格大于 $complexity[0]$。

• 情况 A：如果存在任意 $i$ 使得 $complexity[i] \le complexity[0]$这台计算机 $i$ 永远无法被解锁。因为它的所有前置节点（父节点）的复杂度必须比它小，而根节点 0 是所有解锁路径的起点。如果 $i$ 比起点还小（或相等），它就找不到合法的父节点链。
  • 结论：只要有一个 $complexity[i] \le complexity[0]$，答案就是 0。
• 情况 B：如果所有 $i$ ($i > 0$) 都满足 $complexity[i] > complexity[0]$让我们检查计算机 0 能否直接解锁其他所有计算机：
  • 对于任意 $i > 0$，条件 1 ($0 < i$) 恒成立。
  • 对于任意 $i > 0$，条件 2 ($complexity[0] < complexity[i]$) 也成立（基于当前假设）。
  • 推论：计算机 0 是所有其他计算机的合法父节点。

3. 排列组合计算

如果所有其他计算机 $i$ 都能被计算机 0 直接解锁，这意味着什么？

• 在排列中，只要计算机 0 出现（它必须是第一个，因为它是唯一的初始源），所有其他的计算机 $1$ 到 $n-1$ 就立刻满足了解锁条件（因为它们都可以选 0 作为父节点）。
• 既然所有后续计算机在 0 解锁后都变成了“可解锁”状态，那么它们之间的后续顺序就不再受限了。你可以先解锁 1，再解锁 2；也可以先解锁 2，再解锁 1。题目只要求“存在”一个已解锁的父节点，而 0 永远在那里。

因此，如果所有 $complexity[i] > complexity[0]$，题目就简化为：

• 固定 0 在排列的第一位。
• 剩下的 $n-1$ 个元素可以任意排列。

答案即为 $(n-1)!$ 的全排列数量。

算法步骤

1. 检查合法性：遍历数组 complexity（从索引 1 开始）。如果发现任何 complexity[i] <= complexity[0]，直接返回 0。
2. 计算阶乘：如果所有元素都合法，计算 $(n-1)! \pmod{10^9 + 7}$。

具体代码

func countPermutations(complexity []int) int {
	n := len(complexity)
	rootVal := complexity[0]
	const mod = 1_000_000_007

	ans := 1
	// 从下标 1 开始遍历到 n-1
	for i := 1; i < n; i++ {
		// 1. 检查逻辑：如果发现非法节点，直接返回 0
		if complexity[i] <= rootVal {
			return 0
		}
		
		// 2. 计算逻辑：累乘当前的 i，计算 (n-1)!
		// i 正好是从 1 到 n-1，符合阶乘定义
		ans = (ans * i) % mod
	}

	return ans
}