題目描述: 有 n 個人,richer[i] = [ai, bi] 表示 ai 比 bi 更有錢。quiet[i] 表示第 i 個人的安靜程度(數值越小越安靜)。對於每個人 x,找出所有比 x 有錢(含 x 自己)的人中,最安靜的那個人。
解題思路:
時間複雜度:O(n + E) — n 為人數,E 為 richer 關係數量。每個節點和邊只處理一次
空間複雜度:O(n + E) — 圖的鄰接表和遞迴堆疊
1. Build directed graph: for each (a, b) in richer, add edge b -> a
2. Initialize answer array with -1 (unvisited)
3. For each person i (0 to n-1):
a. Call DFS(i)
4. DFS(node):
a. If ans[node] != -1, return (already computed)
b. Set ans[node] = node (self is the quietest so far)
c. For each richer neighbor next:
- DFS(next)
- If quiet[ans[next]] < quiet[ans[node]]:
- ans[node] = ans[next]
5. Return answer array拓撲排序 + BFS:先計算每個節點的入度,從入度為 0 的節點(最有錢的人)開始 BFS。處理時將答案傳播到比自己窮的人。這避免了遞迴,適合擔心遞迴深度的情況。
暴力 DFS(無記憶化):對每個人分別做一次完整的 DFS。時間複雜度 O(n*(n+E)),在人數和關係多時會超時,但代碼最簡單。