leetcode 1395. 统计作战单位数

题目链接：1395. 统计作战单位数

原题：

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 中的元素都是唯一的

---

题意：

现在有N个不重复的数排成一排，求其所有长度为3的子序列中，单调递增和单调递减的个数

题解：

在长度为3的子序列中，我们可以枚举中间数字，那么这个长度为3的序列可以拆成两部分，前两个数字和后两个数字。
例如，对于一个单调递增的子序列 a[i] < a[j] < a[k] ，其中 i < j < k ，可以分为 a[i] < a[j]，i < j 和 a[j] < a[k]，j < k。并且这个中间值前后是不影响的，那么我们枚举中间的a[j]时，只需要将 它前面比a[j]小的个数 与 它后面比a[j]大的个数 相乘即可
同理，对于 a[i] > a[j] > a[k]， i < j < k 的情况，我们只需要将 它前面比a[j]大的个数 与 它后面比a[j]小的个数 相乘即可

---

代码（先自己实现，解决不了再查看代码哦）：

class Solution {
public:int f[1010][2], g[1010][2];int numTeams(vector<int>& rating) {int i, j, k, n = rating.size(), ans;memset(f, 0, sizeof(f));//f[i][0/1]为第i个数之前比它小/大的数的个数memset(g, 0, sizeof(g));//g[i][0/1]为第i个数之后比它小/大的数的个数for(i = 0; i < n; i++){for(j = 0; j < i; j++){if(rating[j] < rating[i]) f[i][0]++;else if(rating[j] > rating[i]) f[i][1]++;}}for(i = 0; i < n; i++){for(j = i + 1; j < n; j++){if(rating[j] < rating[i]) g[i][0]++;else if(rating[j] > rating[i]) g[i][1]++;}}ans = 0;for(i = 0; i < n; i++){ans += f[i][0] * g[i][1];ans += f[i][1] * g[i][0];}return ans;}
};