題目描述:給定整數陣列 nums,找出最長嚴格遞增子序列(LIS)的長度。
解題思路:O(n log n) 解法使用耐心排序(patience sorting)的概念。維護陣列 tails,其中 tails[i] 是長度為 i+1 的 LIS 結尾的最小可能值。對每個新元素,用二分搜尋找到 tails 中第一個 >= 當前元素的位置,替換之(或擴展 tails)。tails 的長度即為 LIS 長度。
時間複雜度:O(n log n) — 每個元素做一次二分搜尋。
空間複雜度:O(n) — tails 陣列最長為 n。
1. Initialize empty tails array 2. For each num in nums: a. Binary search for leftmost index lo where tails[lo] >= num b. If lo == len(tails): append num (longer IS found) c. Else: tails[lo] = num (replace with smaller tail) 3. Return len(tails)
DP 嵌套迴圈 O(n²) 時間,O(n) 空間:維護 dp[i],對每個 i 掃描所有 j < i — 時間複雜度更差但邏輯簡單。
貪心 + 二分 O(n log n) 時間,O(n) 空間:本解法核心,維護遞增尾數組,二分插入位置 — 此即本方法。