[leetcode] 1395. Count Number of Teams

Description

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.length1 <= n <= 2001 <= rating[i] <= 10^5

分析

题目的意思是：求出3个递增或者3个递减数的个数，这道题我没有做出来，参考了一下别人的实现，首先从左到右进行遍历，lt表示的是j左边比第j位置小的数的个数，gt表示的是j右边比位置j大的数的个数，ltgt就是递增的数目，递减则就是剩下的数的乘积：(j-lt)(n-(j+1)-gt).当然还有动态规划的解法，需要两个数组存放中间值，我还没看懂哈哈，有兴趣可以跟我一起研究一下，请参考我给的链接.

代码

class Solution: def numTeams(self, rating: List[int]) -> int: n=len(rating) res=0 for j in range(1,n-1): lt=sum(rating[i]<rating[j] for i in range(j)) gt=sum(rating[j]<rating[k] for k in range(j,n)) res+=lt*gt+(j-lt)*(n-j-gt-1) return res

参考文献

[LeetCode] Simple & Easy Solution by Python 3 [leetcode]Python | clean DP solution O(n^2) 92 % fast