题目描述

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
  请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。

样例

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

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

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

提示：

• n == rating.length
• 1 <= n <= 200
• 1 <= rating[i] <= 10^5

算法分析

枚举
从1到n - 2枚举所有元素

• 再暴力枚举左边的元素，找到比当前数小的个数left1，和比当前大的个数right1
• 再暴力枚举右边的元素，找到比当前数大的个数left2，和比当前数小的个数right2

总个数为left1 * right1 + left2 * right2

时间复杂度$O(n^2)$

Java 代码

class Solution {
    public int numTeams(int[] rating) {
        int n = rating.length;
        int res = 0;
        for(int i = 1;i <= n - 2;i ++)
        {
            int left1 = 0,left2 = 0;
            int right1 = 0,right2 = 0;
            for(int j = i - 1;j >= 0;j --)
            {
                if(rating[j] < rating[i]) left1 ++;
                if(rating[j] > rating[i]) left2 ++;
            }
            for(int j = i + 1;j < n;j ++)
            {
                if(rating[j] > rating[i]) right1 ++;
                if(rating[j] < rating[i]) right2 ++;
            }
            res += left1 * right1 + left2 * right2;
        }
        return res;
    }
}