Medium

题目描述

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

房间里有 n 台被锁定的计算机，标签从 0 到 n - 1，每台都有自己独特的密码。计算机 i 的密码复杂度为 complexity[i]。

标签为 0 的计算机密码已经被解密，作为根节点。所有其他计算机必须使用它或另一台之前已解锁的计算机来解锁，遵循以下信息：

  • 你可以使用计算机 j 的密码来解密计算机 i 的密码，其中 j 是任何小于 i 且复杂度更低的整数。（即 j < i 且 complexity[j] < complexity[i]）
  • 要解密计算机 i 的密码，你必须已经解锁了一台计算机 j，使得 j < i 且 complexity[j] < complexity[i]。

找出表示计算机可以解锁的有效顺序的排列 [0, 1, 2, …, (n - 1)] 的数量，从计算机 0 作为唯一初始解锁的计算机开始。

由于答案可能很大，返回结果模 10^9 + 7。

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

示例 1：

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

输出：2

示例 2：

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

输出：0

约束条件：

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

解题思路

这道题的关键在于理解解锁规则：要解锁计算机 i，必须存在一台已解锁的计算机 j，满足 j < i 且 complexity[j] < complexity[i]。

首先分析题目条件：

  1. 计算机 0 已经解锁，作为根节点
  2. 要解锁计算机 i（i > 0），必须存在 j < i 且 complexity[j] < complexity[i] 的已解锁计算机

关键观察：如果 complexity[0] 不是数组中的最小值，或者存在其他元素与 complexity[0] 相等，那么某些计算机将无法解锁。

具体分析：

  • 如果 complexity[0] 不是唯一最小值，那么存在某个 i > 0，使得 complexity[i] ≤ complexity[0]
  • 对于这样的 i，不存在 j < i 且 complexity[j] < complexity[i]，因此无法解锁

当 complexity[0] 是唯一最小值时：

  • 所有其他计算机都可以通过计算机 0 解锁（因为它们的复杂度都大于 complexity[0]）
  • 计算机 0 必须排在第一位
  • 剩余 n-1 台计算机可以任意排列

因此答案为：

  • 如果 complexity[0] 是唯一最小值：(n-1)!
  • 否则：0

代码实现

class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        const int MOD = 1e9 + 7;
        int n = complexity.size();
        
        // 检查complexity[0]是否是唯一最小值
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
        }
        
        // 计算(n-1)!
        long long result = 1;
        for (int i = 1; i < n; i++) {
            result = (result * i) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(complexity)
        
        # 检查complexity[0]是否是唯一最小值
        for i in range(1, n):
            if complexity[i] <= complexity[0]:
                return 0
        
        # 计算(n-1)!
        result = 1
        for i in range(1, n):
            result = (result * i) % MOD
        
        return result

public class Solution {
    public int CountPermutations(int[] complexity) {
        const int MOD = 1000000007;
        int n = complexity.Length;
        
        // 检查complexity[0]是否是唯一最小值
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
        }
        
        // 计算(n-1)!
        long result = 1;
        for (int i = 1; i < n; i++) {
            result = (result * i) % MOD;
        }
        
        return (int)result;
    }
}

var countPermutations = function(complexity) {
    const MOD = 1e9 + 7;
    const n = complexity.length;
    
    // 检查complexity[0]是否是唯一最小值
    for (let i = 1; i < n; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
    }
    
    // 计算(n-1)!
    let result = 1;
    for (let i = 1; i < n; i++) {
        result = (result * i) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

相关题目