这题好像 水蛮深的 做法很多
自己是先用了个O(N^2) 先能过吧
直觉是想应该可以O(NlogN)啦
毕竟unique rating
随便一个binary search方法应该都可以 但懒想
先去上班晚上再来看看其他人的写法
我这应该就算brute force吧
大概就是
先init各rating后有多少rating是比他大的 全记下来
然后就forloop加加加加加
最后反过来再做一次 对ㄚ==
def numTeams(self, rating: List[int]) -> int:
n = len(rating)
def helper(rating):
ushiros = defaultdict(list)
for i in range(n):
cnt_cur = 0
for j in range(i, n):
if rating[j] > rating[i]:
ushiros[rating[i]].append(rating[j])
ans = 0
for num in rating:
for num2 in ushiros[num]:
ans += len(ushiros[num2])
return ans
return helper(rating) + helper(rating[::-1])