給定一個整數陣列
nums，找出最長嚴格遞增子序列的長度。子序列不需要連續但需保持原始順序。
Example:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4
Intuition
TIP
DP 解法：以每個元素結尾的 LIS 長度；進階：用 patience sorting 搭配二分搜尋做到 O(n log n)。
- DP：對每個
i，找前面所有比nums[i]小的j，取最長 + 1 - 進階：維護一個
tails陣列，tails[k]是長度為k+1的遞增子序列的最小結尾元素 - 用二分搜尋找
tails中第一個 >= 當前元素的位置來更新
Approaches
1. DP O(n^2) — O(n^2) / O(n)
- Idea:
dp[i]= 以nums[i]結尾的最長遞增子序列長度 - Time:
O(n^2) - Space:
O(n)
class Solution {
fun lengthOfLIS(nums: IntArray): Int {
val dp = IntArray(nums.size) { 1 }
for (i in 1 until nums.size) {
for (j in 0 until i) {
if (nums[j] < nums[i]) {
dp[i] = maxOf(dp[i], dp[j] + 1)
}
}
}
return dp.max()
}
}⭐ 2. Patience Sorting + Binary Search — O(n log n) / O(n)
- Idea: 維護遞增的
tails陣列，用二分搜尋決定插入或替換位置 - Time:
O(n log n) - Space:
O(n)
class Solution {
fun lengthOfLIS(nums: IntArray): Int {
val tails = mutableListOf<Int>()
for (num in nums) {
var lo = 0; var hi = tails.size
while (lo < hi) {
val mid = (lo + hi) / 2
if (tails[mid] < num) lo = mid + 1 else hi = mid
}
if (lo == tails.size) tails.add(num) else tails[lo] = num
}
return tails.size
}
}🔑 Takeaways
- Pattern: LIS 是經典 DP 問題，O(n log n) 解法是面試進階考點
- Key trick:
tails陣列不是實際的 LIS，但它的長度就是 LIS 的長度；二分搜尋找的是 lower bound