1395. Count Number of Teams

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
• A team is valid if:  (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

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

---

给定一个数组，要求找出这样的升序或者降序的三元组数目。

竞赛阶段，由于n的范围较小，首先尝试暴力O(n^3)解法，代码如下：

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

本代码提交AC，用时204MS。

还有更优的O(n^2)的解法。对于每个士兵，统计其左边小于它的数目，和右边大于它的数目，则这两个数相乘即为该士兵能组成的升序数目，类似的可以算到该士兵能组成的降序数目。代码如下：

class Solution {
public:
	int numTeams(vector<int>& rating) {
		int ans = 0, n = rating.size();
		for (int i = 1; i < n - 1; ++i) {
			vector<int> less_num(2, 0), greater_num(2, 0);
			for (int j = 0; j < n; ++j) {
				if (rating[j] < rating[i])++less_num[j < i];
				else if (rating[j] > rating[i])++greater_num[j > i];
			}
			ans += less_num[1] * greater_num[1] + less_num[0] * greater_num[0];
		}
		return ans;
	}
};

本代码提交AC，用时12MS。