MediumRating 1344
1395. Count Number of Teams
arraydynamic-programmingbinary-indexed-treesegment-tree
解題說明
Count Number of Teams
題目描述: 給定一個整數陣列 rating,選擇 3 名士兵組成一支隊伍,要求索引 (i, j, k) 滿足 i < j < k 且 rating 嚴格遞增或嚴格遞減。求總共有多少種選法。
解題思路: 對於每個中間位置 j,分別統計左邊比 rating[j] 小的數量 leftSmaller 和右邊比 rating[j] 大的數量 rightGreater,則通過 j 的遞增三元組數量為 leftSmaller × rightGreater。同理,左邊比 rating[j] 大的數量 leftGreater 和右邊比 rating[j] 小的數量 rightSmaller 相乘得到遞減三元組數量。對所有 j 求和即為答案。
C++ 解法
複雜度分析
時間複雜度:O(n²) — 對每個中間元素 j,遍歷左右兩側
空間複雜度:O(1) — 只使用常數額外空間
虛擬碼
1. For each middle index j from 1 to n-2: a. Count leftSmaller: elements before j that are smaller than rating[j] b. Count leftGreater: elements before j that are larger than rating[j] c. Count rightSmaller: elements after j that are smaller than rating[j] d. Count rightGreater: elements after j that are larger than rating[j] e. Add leftSmaller * rightGreater (ascending) + leftGreater * rightSmaller (descending) to result 2. Return result
其他解法
方法一:Binary Indexed Tree (BIT) 使用 BIT 動態維護已遍歷元素的排名。從左到右遍歷,可以用 BIT 快速查詢 leftSmaller 和 leftGreater。時間複雜度 O(n log n),適合 n 較大的情況。
方法二:合併排序統計 類似求逆序對的方式,用修改過的合併排序來統計三元組。時間複雜度 O(n log n),但實現複雜度較高。
延伸思考
- 如果隊伍大小不限定為 3,而是任意 k 人,如何推廣你的解法?
- 如果允許非嚴格遞增(即 rating[i] <= rating[j] <= rating[k]),答案會如何變化?
- 如何用 BIT 或線段樹將時間複雜度優化到 O(n log n)?