題目
#

leetcode 300 - Longest Increasing Subsequence (題目說明請點連結)

題目簡述
#

給一個整數陣列 nums，請找出其中最長的遞增子序列（Increasing Subsequence）的長度。
遞增子序列是指在不改變元素順序的情況下，可以刪除某些元素後得到的遞增序列。一個元素也可以是它自己的子序列。

範例
#

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: 最長的遞增子序列是 [2,5,7,101]，長度為 4。

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: 最長的遞增子序列是 [0,1,2,3]，長度為 4。

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1
Explanation: 最長的遞增子序列是 [7]，長度為 1。

解題思路
#

這題要求我們找出陣列中最長的遞增子序列的長度。我們可以使用二分搜尋和tails 陣列的方法來優化解法，將時間複雜度從傳統 DP 的 O(n²) 優化到 O(n log n)。

解法
#

二分搜尋

使用 tails 陣列來記錄每個長度的遞增子序列的最小結尾值
對於每個新元素，使用二分搜尋找到它在 tails 陣列中的插入位置
更新 tails 陣列，保持其遞增性質
最終 tails 陣列的長度就是最長遞增子序列的長度

步驟
#

初始化：
- 創建 tails 陣列，長度等於輸入陣列長度
- 設定 size = 0，記錄當前 tails 陣列的有效長度
遍歷陣列：
- 對於每個元素 n，使用二分搜尋找到插入位置
- 如果 n 大於 tails[mid]，在右半部分搜尋
- 如果 n 小於等於 tails[mid]，在左半部分搜尋
更新 tails 陣列：
- 將 n 插入到找到的位置
- 如果插入位置等於 size，則 size 加 1
返回結果：
- 返回 size，即最長遞增子序列的長度

例子說明
#

nums = [10, 9, 2, 5, 3, 7, 101, 18]

步驟	當前元素	tails 陣列	size	二分搜尋結果	說明
初始化	-	[]	0	-	創建空的 tails 陣列
第 1 步	10	[10]	1	插入位置 0	第一個元素，直接插入
第 2 步	9	[9]	1	插入位置 0	9 < 10，替換 10
第 3 步	2	[2]	1	插入位置 0	2 < 9，替換 9
第 4 步	5	[2, 5]	2	插入位置 1	5 > 2，新增到尾部
第 5 步	3	[2, 3]	2	插入位置 1	3 < 5，替換 5
第 6 步	7	[2, 3, 7]	3	插入位置 2	7 > 3，新增到尾部
第 7 步	101	[2, 3, 7, 101]	4	插入位置 3	101 > 7，新增到尾部
第 8 步	18	[2, 3, 7, 18]	4	插入位置 3	18 < 101，替換 101

最終結果： 4

tails 陣列變化說明：

tails[0] = 2（長度為 1 的遞增子序列的最小結尾值）
tails[1] = 3（長度為 2 的遞增子序列的最小結尾值）
tails[2] = 7（長度為 3 的遞增子序列的最小結尾值）
tails[3] = 18（長度為 4 的遞增子序列的最小結尾值）

最長遞增子序列： [2, 3, 7, 18] 或 [2, 3, 7, 101]

完整程式碼
#

java

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 創建 tails 陣列，用來記錄每個長度的遞增子序列的最小結尾值
        int[] tails = new int[nums.length];
        // size 記錄當前 tails 陣列的有效長度
        int size = 0;

        // 遍歷陣列中的每個元素
        for (int n : nums) {
            // 使用二分搜尋找到當前元素在 tails 陣列中的插入位置
            int left = 0, right = size;

            while (left < right) {
                // 計算中間位置
                int mid = (left + right) / 2;

                if (tails[mid] < n) {
                    // 如果當前元素大於 tails[mid]，在右半部分搜尋
                    left = mid + 1;
                } else {
                    // 如果當前元素小於等於 tails[mid]，在左半部分搜尋
                    right = mid;
                }
            }

            // 將當前元素插入到找到的位置
            tails[left] = n;
            // 如果插入位置等於 size，說明新增了一個長度
            if (left == size) {
                size++;
            }
        }
        
        // 返回最長遞增子序列的長度
        return size;
    }
}

DP 動態規劃解法
#

除了上述的二分搜尋解法，我們也可以使用傳統的動態規劃（Dynamic Programming）來解決這個問題。雖然時間複雜度較高，但思路更直觀易懂。

解題思路
#

狀態定義：

dp[i] 表示以 nums[i] 結尾的最長遞增子序列的長度

狀態轉移方程：

對於每個位置 i，我們需要檢查所有 j < i 的位置
如果 nums[j] < nums[i]，則可以將 nums[i] 接在 nums[j] 後面
dp[i] = max(dp[j] + 1)，其中 j 滿足 0 ≤ j < i 且 nums[j] < nums[i]

初始化：

所有 dp[i] = 1，因為每個元素本身就是長度為 1 的遞增子序列

步驟
#

初始化 DP 陣列： 創建長度為 n 的陣列，所有值設為 1
填表過程： 對於每個位置 i，檢查所有前面的位置 j
狀態轉移： 如果 nums[j] < nums[i]，更新 dp[i] = max(dp[i], dp[j] + 1)
找出最大值： 遍歷 DP 陣列，找出最大值

完整程式碼
#

java

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 邊界條件檢查
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        // dp[i] 表示以 nums[i] 結尾的最長遞增子序列的長度
        int[] dp = new int[n];
        
        // 初始化：每個元素本身就是長度為 1 的遞增子序列
        Arrays.fill(dp, 1);
        
        // 填表過程
        for (int i = 1; i < n; i++) {
            // 檢查所有前面的位置
            for (int j = 0; j < i; j++) {
                // 如果 nums[j] < nums[i]，可以將 nums[i] 接在 nums[j] 後面
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        // 找出 DP 陣列中的最大值
        int maxLength = 1;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }
        
        return maxLength;
    }
}

DP 解法時間複雜度
#

時間複雜度：O(n²)，其中 n 是陣列的長度
- 外層迴圈：O(n)
- 內層迴圈：O(n)
- 總時間複雜度為 O(n²)
空間複雜度：O(n)
- 需要創建 DP 陣列來儲存中間結果

兩種解法比較
#

特性	二分搜尋解法	動態規劃解法
時間複雜度	`O(n log n)`	`O(n²)`
空間複雜度	`O(n)`	`O(n)`
實現難度	較難	較簡單
思路直觀性	較難理解	容易理解
適用場景	追求效率	學習和理解