主題
題目連結：
題目意譯：
你想要建造一些障礙賽道。你被給定一個索引值從 0 開始的長度為 n 之整數陣列 obstacles，其中 obstacles[i] 代表著第 i 個障礙物的高度。
對於每個介於 0 到 n - 1（含端點）的索引值 i，從 obstacles 中找到最長的障礙賽道之長度，使得：
你從 0 到 i（含端點）這些索引值中選出任意數量的對應障礙物。
你必須在賽道中包含第 i 個障礙物。
你必須按照障礙物原先出現於 obstacles 的順序選擇並放置障礙物。
每個障礙物（除了第一個）都高於或等於排於它之前的障礙物。
回傳一長度為 n 的陣列 ans，其中 ans[i] 為如上所述對於索引值 i 的最長的障礙賽道之長度。
限制：
n == obstacles.length
1 ≦ n ≦ 10 ^ 5
1 ≦ obstacles[i] ≦ 10 ^ 7
範例測資：
範例 1：
輸入： obstacles = [1,2,3,2]
輸出： [1,2,3,3]
解釋： The longest valid obstacle course at each position is:
- i = 0: [1], [1] 為長度 1。
- i = 1: [1,2], [1,2] 為長度 2。
- i = 2: [1,2,3], [1,2,3] 為長度 3。
- i = 3: [1,2,3,2], [1,2,2] 為長度 3。
範例 2：
輸入： obstacles = [2,2,1]
輸出： [1,2,1]
解釋： The longest valid obstacle course at each position is:
- i = 0: [2], [2] 為長度 1。
- i = 1: [2,2], [2,2] 為長度 2。
- i = 2: [2,2,1], [1] 為長度 1。
範例 3：
輸入： obstacles = [3,1,5,6,4,2]
輸出： [1,1,2,3,2,2]
解釋： The longest valid obstacle course at each position is:
- i = 0: [3], [3] 為長度 1。
- i = 1: [3,1], [1] 為長度 1。
- i = 2: [3,1,5], [3,5] 為長度 2。 [1,5] 同樣是可行的。
- i = 3: [3,1,5,6], [3,5,6] 為長度 3。 [1,5,6] 同樣是可行的。
- i = 4: [3,1,5,6,4], [3,4] 為長度 2。 [1,4] 同樣是可行的。
- i = 5: [3,1,5,6,4,2], [1,2] 為長度 2。
解題思維：
可以看到我們等同是要為每個索引值 i 所代表的子陣列 [0, i] 找出其最長遞增子序列（Longest Increasing Subsequence，LIS）的長度。
（註：原 LIS 是求整個數列的某個子序列，該子序列不一定包含最後一個數字。題目的版本要包含結尾數字）
當然，可想而知，如果我們直接為每個子陣列都跑一次 O(n log n) 的 LIS（如這題），那我們將得到一個總體時間複雜度為 O(n ^ 2 log n) 的演算法。也就是慢到要命。
這時我們仔細看一下 O(n log n) 的 LIS 演算法的架構：
每當有一新數字進來之後，判斷此數有無比現在 LIS 結尾的數值大。
一：如果此數大於 LIS 的結尾，那就直接放到 LIS 結尾的後面，成為新的結尾。
二：反之，此數小於結尾，則用二分搜尋法（Binary Search）去找到在 LIS 由左數來第一個大於此數的數字，並將其替代掉。（因為此數較小，所以「可能」可以接得更長）
因此當我們求完子陣列 [0, i] 的 LIS 長度後，要求 [0, i + 1] 時，可以看到：
當 obstacles[i + 1] ≧ obstacles[i] 的 LIS 結尾時，因此我們可以直接接在 [0, i] 的 LIS 的後面。因此 [0, i + 1] 的 LIS 之長度為 [0, i] 的 LIS 長度 + 1；
反之，我們需要利用二分搜尋法找到在 [0, i] 的 LIS 中可以用 obstacles[i + 1] 取代哪個數字（假設那個數字在索引值 K 的位置），則此時我們可以看到符合題目要求（包含 obstacles[i + 1]）的 LIS 長度為 K + 1（因為索引值 K 前的數字都小於 obstacles[i + 1]）。
因此我們只需稍微修改原本的 O(n log n) 的 LIS 演算法即可得出所求的每個位置之最長障礙賽道之長度。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
