這題好像 水蠻深的 做法很多
自己是先用了個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])