演算法高階・堆積與串流

k 個 Kafka partition 各自送來一串依時間戳排序的事件，要合併成一條全域有序的串流寫進倉儲。

輸入：

第 1 行：k

接下來 k 行：每行是該 partition 的事件，格式「時間戳:事件代碼」，空白分隔，已依時間戳由小到大排序

輸出：一行，合併後的事件代碼（空白分隔），依時間戳由小到大；時間戳相同時，partition 編號（輸入順序，從 0 起）小的在前。

要求 O(N log k)：不要把全部事件丟進一個串列再排序。

範例輸入：

2

1:x 4:y

2:p 4:q

範例輸出：

x p y q

類型對應：LeetCode「Merge k Sorted Lists」類（情境與敘述為本平台改寫）。

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。本題在瀏覽器內以 Pyodide 執行，只用標準函式庫。先把全部輸入讀完再輸出，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。

監控面板要即時顯示「目前為止所有 API 延遲的中位數」。延遲一筆一筆進來，每進來一筆就要更新中位數。

輸入：一行，空白分隔的整數（毫秒）

輸出：一行，每進來一筆後的中位數，以空白分隔。個數為偶數時取中間兩數平均；中位數是整數就印整數，否則印到小數 1 位（例如 12.5）。

要求每筆 O(log n)：不要每次都排序。

範例輸入：

5 15 1 3

範例輸出：

5 10 5 4

類型對應：LeetCode「Find Median from Data Stream」類（情境與敘述為本平台改寫）。

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。本題在瀏覽器內以 Pyodide 執行，只用標準函式庫。先把全部輸入讀完再輸出，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。

風控要算每支股票「近 k 個交易日的最高收盤價」，每天一個值。

輸入：

第 1 行：n k

第 2 行：n 個整數收盤價

輸出：一行，從第 k 天起每天的近 k 日最高價（共 n - k + 1 個），以空白分隔。

要求 O(n)：用單調遞減的雙端佇列，不要每次取 max(視窗)。

範例輸入：

6 2

3 1 4 1 5 9

範例輸出：

3 4 4 5 9

類型對應：LeetCode「Sliding Window Maximum」類（情境與敘述為本平台改寫）。

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。本題在瀏覽器內以 Pyodide 執行，只用標準函式庫。先把全部輸入讀完再輸出，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。