LeetCode - Longest Increasing Subsequence（最長遞增子序列）

題目描述

給定一個整數數組 nums，請你找出其中的最長遞增子序列的長度。

遞增子序列 是一個子序列，其中所有元素都是遞增的，即對於任意的 i < j，都有 nums[i] < nums[j]。

範例：

輸入：nums = [10, 9, 2, 5, 3, 7, 101, 18]
輸出：4
解釋：最長的遞增子序列是 [2, 3, 7, 101]，其長度為 4。

輸入：nums = [0, 1, 0, 3, 2, 3]
輸出：4
解釋：最長的遞增子序列是 [0, 1, 2, 3]，其長度為 4。

輸入：nums = [7, 7, 7, 7, 7, 7]
輸出：1
解釋：最長的遞增子序列是 [7]，其長度為 1。

限制：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

解法思路

這道題目可以使用動態規劃來解決。定義一個數組 dp，其中 dp[i] 表示以 nums[i] 結尾的最長遞增子序列的長度。

動態規劃步驟

1. 初始化：創建一個 dp 數組，長度與 nums 相同，初始值為 1，因為每個元素自身可以視為長度為 1 的遞增子序列。
2. 遞推公式：對於每個元素 nums[i]（從 1 到 n-1），檢查前面所有的元素 nums[j]（0 到 i-1），若 nums[j] < nums[i]，則可以更新 dp[i]： [ dp[i] = \max(dp[i], dp[j] + 1) ]
3. 結果：最終返回 dp 數組中的最大值，這就是整個數組中的最長遞增子序列的長度。

代碼實現

以下是 Python 的實現：

def lengthOfLIS(nums):
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

代碼解析

1. 邊界條件：檢查 nums 是否為空，若為空則返回 0。
2. 初始化 dp 數組：設置每個元素的初始值為 1。
3. 更新 dp：使用兩層循環，對每個元素，檢查其前面的元素是否滿足遞增條件，並更新 dp。
4. 返回結果：返回 dp 數組中的最大值，即最長遞增子序列的長度。

時間和空間複雜度

• 時間複雜度：O(n^2)，需要兩層循環遍歷每一對元素。
• 空間複雜度：O(n)，使用 dp 數組儲存每個位置的最長遞增子序列長度。

空間優化

可以使用二分搜尋來優化解法，將時間複雜度降到 O(n log n)。

使用二分搜尋的代碼實現

import bisect

def lengthOfLIS(nums):
    if not nums:
        return 0

    dp = []
    
    for num in nums:
        pos = bisect.bisect_left(dp, num)
        if pos == len(dp):
            dp.append(num)
        else:
            dp[pos] = num

    return len(dp)

二分搜尋的解法解析

1. 使用 dp 列表：dp 列表儲存目前已知的遞增子序列的末尾元素。
2. 二分搜尋：對於每個元素 num，找到在 dp 中的插入位置，若該位置等於 dp 的長度，則表示可以新增一個元素，否則更新該位置的值。
3. 返回結果：dp 的長度即為最長遞增子序列的長度。

時間和空間複雜度（空間優化版本）

• 時間複雜度：O(n log n)，因為對每個元素進行一次二分搜尋。
• 空間複雜度：O(n)，儲存當前的遞增子序列。