Medium

题目描述

n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。

每 3 个士兵可以组成一个作战单位，分组规则如下：

  • 从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
  • 作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n

请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。

示例 1：

输入：rating = [2,5,3,4,1]
输出：3
解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。

示例 2：

输入：rating = [2,1,3]
输出：0
解释：根据题目条件，我们无法组建作战单位。

示例 3：

输入：rating = [1,2,3,4]
输出：4

提示：

  • n == rating.length
  • 3 <= n <= 1000
  • 1 <= rating[i] <= 10^5
  • rating 中的所有整数都是 唯一 的

解题思路

这道题要求统计满足递增或递减条件的三元组数量。我们可以用多种方法来解决：

方法一：暴力枚举（推荐）

最直观的方法是三重循环枚举所有可能的三元组 (i,j,k)，检查是否满足 rating[i] < rating[j] < rating[k] 或 rating[i] > rating[j] > rating[k]。

方法二：中心枚举优化

以每个位置 j 为中间元素，分别统计左边比它小/大的元素个数和右边比它大/小的元素个数，然后相乘得到以 j 为中心的合法三元组数量。

对于递增序列：左边小于 rating[j] 的个数 × 右边大于 rating[j] 的个数 对于递减序列：左边大于 rating[j] 的个数 × 右边小于 rating[j] 的个数

这种方法时间复杂度仍为 O(n²)，但常数较小，实际运行效率更高。

方法三：动态规划

可以用 DP 的思想，dp[i][0] 表示以位置 i 结尾的长度为2的递增序列个数，dp[i][1] 表示递减序列个数。不过对于这道题，中心枚举法已经足够优秀。

考虑到题目数据规模（n ≤ 1000），暴力枚举法简单直接，是最好的选择。

代码实现

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        int count = 0;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                        (rating[i] > rating[j] && rating[j] > rating[k])) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        count = 0
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if ((rating[i] < rating[j] < rating[k]) or 
                        (rating[i] > rating[j] > rating[k])):
                        count += 1
        
        return count

public class Solution {
    public int NumTeams(int[] rating) {
        int n = rating.Length;
        int count = 0;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                        (rating[i] > rating[j] && rating[j] > rating[k])) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

var numTeams = function(rating) {
    const n = rating.length;
    let count = 0;
    
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                    (rating[i] > rating[j] && rating[j] > rating[k])) {
                    count++;
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n³)三重循环枚举所有可能的三元组
空间复杂度O(1)只使用常数级别的额外空间