300. Longest Increasing Subsequence

Medium

Description

給定一個整數陣列 nums，找出最長嚴格遞增子序列的長度。子序列不需要連續但需保持原始順序。

Example:

Input: nums = [10,9,2,5,3,7,101,18] Output: 4

Intuition#

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)#

概念: dp[i] = 以 nums[i] 結尾的最長遞增子序列長度
時間複雜度: O(n^2)
空間複雜度: 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#

概念: 維護遞增的 tails 陣列，用二分搜尋決定插入或替換位置
時間複雜度: O(n log n)
空間複雜度: 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) 解法是面試進階考點
關鍵技巧: tails 陣列不是實際的 LIS，但它的長度就是 LIS 的長度；二分搜尋找的是 lower bound