题目描述:
python提交:O(N^3)
class Solution: def numTeams(self, rating: List[int]) -> int: ans = 0 for i in range(len(rating)): for j in range(i,len(rating)): for k in range(j,len(rating)): if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]: ans += 1 return ans
java提交:O(N^3)
class Solution { public int numTeams(int[] rating) { int ans = 0; for(int i=0;i<rating.length;i++){ for(int j=i+1;j<rating.length;j++){ for(int k=j+1;k<rating.length;k++){ if(rating[i]<rating[j] &&rating[j]<rating[k]||rating[i]>rating[j] &&rating[j]>rating[k]) ans += 1; } } } return ans; } }
优化:
class Solution: def numTeams(self, rating: List[int]) -> int: def calc(S): n=len(S) re=0 for i in range(n): l=0 r=0 for j in range(0,i): if S[j]<S[i]: l+=1 for j in range(i+1,n): if S[j]>S[i]: r+=1 re+=l*r return re ans=calc(rating) rating.reverse() ans+=calc(rating) return ans