HardRating 1933
1964. Find the Longest Valid Obstacle Course at Each Position
arraybinary-searchbinary-indexed-tree
解題說明
Find the Longest Valid Obstacle Course at Each Position
題目描述：
給定一個整數陣列 obstacles，對於每個位置 i，找出以 obstacles[i] 結尾的最長非遞減子序列的長度。即找出索引 i1 < i2 < ... < ik = i，使得 obstacles[i1] <= obstacles[i2] <= ... <= obstacles[ik]，求最大的 k。
解題思路： 這是經典「最長非遞減子序列」（LIS 的變體）問題，差別在於允許相等元素且需要對每個位置輸出答案。
- 維護一個陣列
tails，tails[j]表示長度為j+1的非遞減子序列中，末尾元素的最小值。 - 對於每個
obstacles[i]，使用二分搜尋在tails中找到第一個嚴格大於obstacles[i]的位置（upper_bound）。 - 若找到位置
pos，則更新tails[pos] = obstacles[i]；若pos等於tails的長度，則在末端追加。 - 當前位置的答案為
pos + 1。
注意使用 upper_bound（而非 lower_bound）是因為允許相等元素。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 對每個元素進行一次二分搜尋，每次 O(log n)。
空間複雜度：O(n) — tails 陣列最大長度為 n。
虛擬碼
1. Initialize empty array tails[]
2. For each i from 0 to n-1:
a. Binary search for the first index pos in tails where tails[pos] > obstacles[i]
(use upper_bound)
b. If pos == len(tails): append obstacles[i] to tails
Else: set tails[pos] = obstacles[i]
c. Set ans[i] = pos + 1
3. Return ans其他解法
Binary Indexed Tree (BIT) 解法 O(n log M)：將障礙物高度離散化後，用 BIT 維護「高度 <= h 的最長子序列長度」。對每個元素查詢 BIT 中 [1, h] 的最大值再加 1，然後更新 BIT。適合值域較小時使用。
Segment Tree 解法 O(n log M)：類似 BIT，但用線段樹支持區間最大值查詢與單點更新。程式碼較長但更通用。
延伸思考
- 如果要求嚴格遞增子序列（不允許相等），二分搜尋應如何修改？
- 如何回溯並實際輸出最長子序列的元素，而不僅是長度？
- 此題與 LeetCode 300 (Longest Increasing Subsequence) 的關鍵差異是什麼？