略譯

原題目連結

給你 n 個士兵，排成一個橫列，士兵死了隊列會靠攏繼續前進，
每個士兵有一個 ID，一開始從最左ID 1 依序排到最右ID n，
給你 m 組死亡報告，每組 i, j 表示士兵ID i 到 j 全死了
對於每組報告，回答死掉的 i 到 j 左邊和右邊士兵各是誰

題解

暴力在陣列上做刪除後靠攏會 TLE
Linked List在搜尋目標士兵 ID 太慢，最糟情況從最右刪回來，
可以劣化到 nm 的複雜度

結合 Linked List 刪除的概念、陣列的搜尋

用陣列存每個士兵的左邊和右邊各是誰

每次刪除可以直接找到被殺的最左士兵和最右士兵
馬上知道最左士兵的左邊，和最右士兵的右邊是誰

然後將他們左邊連到右邊、右邊連到左邊

每一步都是 O(1) 直接解決
總複雜度為 n+m

實作提示

• 左右各留一格，就無須判斷邊界