今天起我們來看另一個有趣的題型：遞增序列(Increasing Subsequence)

目錄

🟨最長遞增子序列

本題取自 Leetcode 300. Longest Increasing Subsequence

題目

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.


Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4


Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1
 

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

分析

本題求給定陣列的子序列當中「最長的嚴格遞增子序列」(Longest Increasing Subsequence，下稱LIS)。

子序列(subsequence)指的是：自陣列當中取任意元素並維持與原陣列相同排序所形成的陣列。例如[A, B, C, D]的子序列包含’[A, D]‘但不包含[B, A](因為排列順序不同)。

嚴格遞增列表(陣列)arr定義為，對所有i>j，arr[i]>arr[j]。

窮舉所有子序列並且判斷是否為嚴格遞增是不現實的，因為這會花費O(2^n x n)的時間複雜度。

比較直覺的做法是：從第一個元素開始往後迭代，每增加一個元素，就尋找「以這個元素為尾端」的LIS。

Brute Force(暴力解)

分治法

以陣列nums = [1, 3, 2, 3, 5]為例：

• 以nums[0]的1結尾的LIS為[1]

• 以nums[1]的3結尾的LIS為？→[1,3]

  • 往前找，因為1<3，所以可以接在[1]後面，形成[1,3]

• 以nums[2]的2結尾的LIS為？→[1,2]

  • 往前找，因為1<2，所以可以接在[1]後面，形成[1,2]
  • 因為3>2，所以不能接在[1,3]後面。

• 以nums[3]的3結尾的LIS為？→[1,2,3]

  • 往前找，因為1<3，所以可以接在[1]後面，形成[1,3]
  • 因為3==3，所以不能接在[1,3]後面。
  • 因為2<3，所以可以接在[1,2]後面，形成[1,2,3]
  • 取最長的[1,2,3]

• 依此類推，以nums[4]的5結尾的LIS為？→[1,2,3,5]

設計狀態、找出轉移式與最小問題

狀態：以lis(i)表示：以nums[i]作為結尾的*最長遞增子序列(LIS)*長度

轉移式：要找出lis(i)，需要：

• 遍歷介於0<=j<i當中的位置j
• 其中，若 nums[j] < nums[i]，則代表尾端接上nums[i]仍然遞增
• 取以上所有符合遞增的lis(j)當中最大值並且+1，即為lis(i)

最小狀態(邊界條件)：lis(0)==1。沒有任何j符合遞增條件時，lis(i)=1

母問題(題目所求)：所有lis(x)當中最大值

Top-Down DP

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        @cache
        def lis(i):
            return 1+max([lis(j) for j in range(i) if nums[j]<nums[i]] or [0])
        return max(lis(i) for i in range(len(nums)))=[]

Bottom-Up DP

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = []
        for i in range(len(nums)):
            dp.append(1+max([dp[j] for j in range(i) if nums[j]<nums[i]] or [0]))

        return max(dp)

複雜度分析

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數 = O(n)，n = len(nums)

計算複雜度為O(n) (max需要遍歷前面每一格的答案)

因此總時間複雜度 = O(n^2)

空間複雜度

空間複雜度 ＝ 狀態數 ＝ O(n)

優化：Greedy (Monotonic Array & Binary Search)

分析前述的解法，可能會感覺這個max有點非效率。至少，我們以人工來尋找LIS的時候，似乎不需要那麼高的複雜度呀。

讓我們用另一個角度來看待這個問題。

以nums = [1, 3, 2, 3]為例來尋找LIS的長度。

但是，這一次我們建立一棵樹(Tree)來記錄LIS。

規則是這樣的：

遍歷nums，對於每一個元素k，我們從樹的最底層(level最大的)往上一層一層尋找節點。如果找到某個節點j且j的值<k，就把k連接在j的下一層。

此舉保證這棵樹只要由上到下的所有路徑都為遞增，且因為我們從下方開始尋找可連接的節點，接上k所形成的遞增數列必定為最長。最終所形成的樹，其樹高(總層數)必定是LIS的長度，亦即題目所求。

如果同一層找到兩個以上的節點符合規則，則將k連接在最小的節點。(設定此規則的原因後述)

前兩個數為遞增，所以可以直接往下接。

從最底層開始嘗試，因為2<3，沒辦法接在3的下面。

因此，往上一層，接在1的下面

下一個數是3，可以接在2的下面。

完成，此時的樹高(level=3)就對應LIS[1,2,3]的長度。

根據前述規則，以[1,3,2,3,5,2,3,4,5]為例，畫出來的樹應該如下圖：

可以發現，這個作法所產生的遞增數列確實能保證為最長，例如下圖，當遍歷到5時，雖然也有[1,3,5]這個數列，但是[1,2,3,5]顯然是更長的。

此外我們還能觀察到本樹的兩個性質：

1.當我們要在樹上增加新的節點時，只需要考慮每一層最小的數即可。

這是一個貪心策略(Greedy)的思維。

根據我們的規則，新的數k必須大於其所連接的節點。

若k大於某一層的某節點，則也必定大於同一層的最小節點。

2.各層的最小節點，會形成一個嚴格遞增數列。

證明如下：

根據我們建立樹的規則，第i層的最小節點min(i)會大於其位於i-1層的母節點parent(i-1)，而這個節點又必定大於或者等於同一層的最小節點min(i-1)。因此，min(i)必定大於min(i-1)

第一個性質，讓我們不需要紀錄整棵樹，而只需要紀錄每一層最小的節點。

在插入新的數k時，尋找比k大的最小節點，並且直接取代這個節點。

例如前面舉例的數列，當進行到[1,3,1,2,3,5,1,2,3]時，整棵樹跟實際上紀錄的「每層最小節點」如下圖：

接著要加入4，整棵樹跟實際上紀錄的「每層最小節點」的操作如下圖：

第二個性質，則讓我們得以使用*二元搜尋法(binary search)*來降低搜尋的時間複雜度。

Bottom-Up DP

from bisect import bisect_left as bs
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lis = []                # 記錄Tree每一層最小節點
        for k in nums:
            idx = bs(lis, k)    # 在lis當中找大於k的最小的數(的位置)
            if idx < len(lis):
                lis[idx] = k    # 取代這個數(因為k是同一層的最小節點)
            else:
                lis.append(k)   # k>所有數：接在最後面
        return len(lis)

因為lis當中的所有數都可能隨著解題而變動，本題較不適合使用Top-Down Approach。

複雜度分析

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數 = O(n)，n = len(nums)

計算複雜度為O(log n) (binary search的時間複雜度)

因此總時間複雜度 = O(n log n)

空間複雜度

空間複雜度 ＝ 狀態數 ＝ O(n)

結語

和前面出現過的DP題稍有不同，這是我們第一次透過對資料結構的改善來優化動態規劃的複雜度。

比較容易搞混的一點是，本題的資料結構並非Monotonic Stack(遞增佇列)。盡管紀錄Tree上每一層的最小節點的lis本身確實符合Monotonic(嚴格遞增)的特性，但我們對其的修改會直接改動中間的值，而非像stack那樣只能pop最尾端的值。因此，充其量可以稱之為Monotonic Array(List)，而非(在這個題型的其他題目中常出現的)Monotonic Stack。

另一個需要注意的重點，本題的lis最終所儲存的值並不一定是真正的LIS，但二者的長度必定相等。舉例來說，[1,3,2,3,5,6,2,4]經過操作之後，lis會記錄[1,2,3,4,6]，但真正長度的LIS是長度相同的[1,2,3,5,6]。因為lis紀錄的是整棵樹每一層最小的數，而非(相連的)LIS。

如果題目要求回答真正的LIS，那麼可以改為真的建立一棵樹，並且用lis來記錄每一層最小的節點，如此一來仍能維持O(n log n)的效率。

以上為Day16的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。

明天會繼續看更多LIS題型的題目。