HardRating 2280
2407. Longest Increasing Subsequence II
arraydivide-and-conquerdynamic-programmingbinary-indexed-treesegment-treequeuemonotonic-queue
解題說明
Longest Increasing Subsequence II
題目描述： 給定整數陣列 nums 和整數 k，找到最長的嚴格遞增子序列，使得子序列中相鄰元素的差值不超過 k。返回該子序列的長度。
解題思路： 這是經典 LIS 的變體，加上了相鄰差值的限制。定義 dp[v] 為以值 v 結尾的最長合法子序列長度。對於 nums[i]，我們需要查詢 dp[nums[i]-k] 到 dp[nums[i]-1] 的最大值，然後 dp[nums[i]] = max_val + 1。
這本質上是一個「區間最大值查詢 + 單點更新」問題，可以用線段樹高效處理。線段樹建在值域上（1 到 max(nums)），每個節點維護該值域範圍內的 dp 最大值。
C++ 解法
複雜度分析
時間複雜度：O(n log M) — 其中 M 為 nums 中的最大值，每次線段樹查詢和更新為 O(log M)
空間複雜度：O(M) — 線段樹大小為 4M
虛擬碼
1. Build a segment tree over value range [0, max(nums)] 2. For each element x in nums: a. Query segment tree for max value in range [x-k, x-1] b. current_length = query_result + 1 c. Update segment tree at position x with current_length (if larger) d. Update global answer 3. Return answer
其他解法
-
BIT（樹狀陣列）+ 座標壓縮：用樹狀陣列維護前綴最大值。需要將查詢範圍 [x-k, x-1] 轉換為前綴查詢。座標壓縮可以降低空間複雜度。時間複雜度相同 O(n log M)。
-
單調佇列 + DP：如果 k 較小，可以用滑動窗口維護 dp 值的最大值。但由於是值域而非索引的窗口，直接使用較困難，通常還是線段樹更通用。
延伸思考
- 如果限制改為相鄰元素差值「至少」為 k（而非至多），如何修改線段樹查詢範圍？
- 如果要找最長的「非嚴格」遞增子序列（允許相等），線段樹查詢範圍需要如何調整？
- 如果 nums 的值域非常大（到 10^9），如何用座標壓縮 + 線段樹解決？