【LeetCode】300. 最長遞增子序列 Longest Increasing Subsequence(C++)

目錄

• • 題目描述
  • 題目大意
  • 動态規劃O(n^2)
  • 複雜度分析
  • 貪心+二分查找
  • 複雜度分析

題目來源：https://leetcode-cn.com/problems/longest-increasing-subsequence/

題目描述

給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。

子序列是由數組派生而來的序列，删除（或不删除）數組中的元素而不改變其餘元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

示例 1：

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

輸出：4

解釋：最長遞增子序列是 [2,3,7,101]，是以長度為 4 。

示例 2：

輸入：nums = [0,1,0,3,2,3]

輸出：4

示例 3：

輸入：nums = [7,7,7,7,7,7,7]

輸出：1

提示：

1 <= nums.length <= 2500

10^4 <= nums[i] <= 10^4

進階：

你可以設計時間複雜度為 O(n2) 的解決方案嗎？

你能将算法的時間複雜度降低到 O(n log(n)) 嗎?

題目大意

• 動态規劃經典應用題，求最長嚴格單調子序列，且子序列不要求連續，但有先後順序，貪心+二分查找的思想經常出現在動态規劃中，先定義題目的狀态

  d p [ i ] = m a x ( d p [ j ] + 1 ) ， 其 中 0 ≤ j ≤ i ， 且 n u m [ j ] ＜ n u m [ i ] dp[i]=max(dp[j]+1)，其中0≤j≤i，且num[j] ＜num[i] dp[i]=max(dp[j]+1)，其中0≤j≤i，且num[j]＜num[i]

動态規劃O(n^2)

經過嵌套循環可得，假如dp[j]的值為2，就相當于到下标j時，已然構成了長度為2的嚴格單調子序列，向下标i擴張時，隻需判斷此時的j是否滿足，nums[j]<nums[i]，滿足條件則向i擴張，更新dp[i]，注意此時是dp[j]+1和dp[i]進行對比，需考慮dp[i]此時已經包括在某個子序列中的長度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size(), ans = 0;
        vector<int> dp(len, 1);
        for(int i = 0 ; i < len ; ++i){
            for(int j = 0 ; j < i ; ++j){
                if(nums[j] < nums[i])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};
           

複雜度分析

• 時間複雜度：O(n^2)。近似為嵌套周遊數組
• 空間複雜度：O(n)。n為數組的大小

貪心+二分查找

• 對于嚴格單調子序列，我們可以維護一個dp數組，根據上面的推理可得一下算法流程
• 設目前已求出的最長上升子序列的長度為len（初始值為1），從前往後周遊數組nums，在周遊到nums[i]時：
  • 如果num[i]>dp[len]，則直接加入到dp數組末尾，并更新len=len+1
  • 否則，在dp數組中二分查找，找到第一個比nums[i]小的數d[k]，并更新d[k+1]=nums[i]

以輸入序列 [0, 8, 4, 12, 2]為例：

第一步插入 0，dp = [0]；

第二步插入 8，dp = [0, 8]；

第三步插入 4，dp = [0, 4]；

第四步插入 12，dp = [0, 4, 12]；

第五步插入 2，dp = [0, 2, 12]。

最終得到最大遞增子序列長度為 3。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len + 1, 0);
        int index = 1;
        dp[1] = nums[0];
        for(int i = 1 ; i < len ; ++i){
            if(dp[index] < nums[i]){
                dp[++index] = nums[i];
            }else{
                int left = 1, right = index, result = -1;
                while(left <= right){
                    int mid = right + ((left - right) >> 1);
                    if(dp[mid] < nums[i])  left = mid + 1;
                    else{
                        if(mid == 0 || dp[mid - 1] < nums[i]){
                            result = mid;
                            break;
                        }
                        else    right = mid - 1;
                    }
                }
                dp[(result != -1) ? result : 1] = nums[i];
            }
        }
        return index;
    }
};
           

複雜度分析

• 時間複雜度：O(nlogn)。二分查找的平均時間複雜度為O(nlogn)，此處的n最壞與數組n相等
• 空間複雜度：O(n)。