題目敘述 Count Number of Teams
給定一個輸入陣列rating，裡面代表每位成員的評分
挑選三位成員，對應到三個index i, j, k 且 i < j < k
如果rating[i] < rating[j] < rating[k] ，則此三人可以組成一隊。或者rating[i] > rating[j] > rating[k] ，則此三人也可以組成一隊。
請問成功組成三人小隊的方法數有多少?
測試範例
Example 1:
Input: rating = [2,5,3,4,1]
Output: 3
Explanation:
成功的組隊方式 (2,3,4), (5,4,1), (5,3,1).
Example 2:
Input: rating = [2,1,3]
Output: 0
Explanation:
無解 無法找到 評分遞減或評分遞增的三人組隊方式
Example 3:
Input: rating = [1,2,3,4]
Output: 4
成功的組隊方式 (1,2,3), (1,2,4), (1,3,4), (2,3,4).
演算法 滑動窗口 + 統計左側右側資訊
假想中央那名成員為在index j 的位置，
統計左方rating 比較小 和 右方rating比較大的成員數量。
如次一來，
遞增排列組隊方法數 = 左方rating比較小的成員數量 * 右方rating比較大的成員數量
遞減排列組隊方法數 = 左方rating比較大的成員數量 * 右方rating比較小的成員數量
最後，用一個for loop，把index j 從頭到尾掃描一遍，累加所有合法的組隊方式即可。
示意圖 滑動窗口 + 統計左側右側資訊
程式碼 滑動窗口 + 統計左側右側資訊
class Solution:
def numTeams(self, rating: List[int]) -> int:
r, size = rating, len( rating )
# compute statistics of sliding range
left_smaller = [ sum( r[i] < r[j] for i in range(0,j) ) for j in range(size) ]
right_bigger = [ sum( r[j] < r[k] for k in range(j+1, size) ) for j in range(size)]
num_of_teams = 0
# j slides from 0 to ( n-1 ), and j stands for the index of middle element
for j in range( 0, size):
num_of_ascending_team = left_smaller[j] * right_bigger[j]
num_of_descending_team = ( j - left_smaller[j] ) * ( size-1 - j - right_bigger[j] )
num_of_teams += ( num_of_ascending_team + num_of_descending_team )
return num_of_teams
複雜度分析
時間複雜度: O(n^2)
預先統計左右兩次資訊，雙層迴圈耗費O(n^2)
累加組隊數量，單層迴圈耗費O(n)
空間複雜度: O(n)
預先統計左右兩次資訊，需要額外的O(n)空間
