300. Longest Increasing Subsequence

发表于 | 分类于 | 浏览 次

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

1
2
3
Input: [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.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

这里有几个需要注意的点：

  1. 如果只有一个元素时，结果该是多少，这是本题答案的最小值。
  2. 这里的incresing是严格的。如果两个元素相等，它们不是incresing的。

解法1：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        vector<int> dp(nums.size(), 1);
        int cnt = 1;        // 注意初值应该是多少
        for(int i=1;i<nums.size();++i){
            for(int j=i-1;j>=0;--j){
                if(nums[j] < nums[i] && dp[j] + 1 > dp[i]){
                    dp[i] = dp[j] + 1;
                }
            }
            cnt = max(cnt, dp[i]);
        }
        return cnt;
    }
};

时间复杂度：O(n^2)
空间复杂度：O(n)

解法2：动态规划+二分查找

初始化一个dp数组，用于存储包括当前元素在内的递增子序列。从左向右遍历，当遇到一个新元素时，如果这个元素比dp数组中最后一个元素还要大，说明这个元素可以加长整个递增子序列，将这个元素加入到dp数组尾部。如果这个新元素比当前找到的最大元素要小，说明这个新元素的存在无法更进一步加长整个递增子序列，但是我们可以用新元素来替换掉已存在的递增子序列中第一个大于该元素的元素。这样做并不会改变目前已经找到的最长递增子序列的长度，但是却实现了逐步用新元素来代替旧的元素形成新的递增子序列。

举一个具体的例子。当输入为[10,9,2,5,3,7,101,18]时，我们使用一个dp数组。以变量i记录循环轮次。

  1. i = 0时，nums[0] = 10, dp为空，所以直接将10加入到dp数组中，此时dp为[10]。
  2. i= 1时，nums[1] = 9，9比dp中最后一个元素小，说明9的加入不会增加递增子序列的长度，但是9仍然有可能与后续元素形成更长的递增子序列。且9比dp中已经存在的第一个比9大的元素（即10）更可能形成更长的递增子序列。所以用9替换10。dp为[9]。
  3. i = 2时，nums[2] = 2，同理用2替换9，dp为[2]。
  4. i = 3时，nums[3] = 5，5比dp中最后一个元素2大，因此，5的加入可以形成更长的递增子序列，直接将5加入到dp中。dp为[2, 5]。
  5. i = 4时，nums[4] = 3，同理用3替换5。dp为[2, 3]。
  6. i = 5时，nums[5] = 7，7比3大，直接将7加入到dp中。dp为[2, 3, 7]。
  7. i = 6时，nums[6] = 101，101比7大，直接加入dp中。dp为[2, 3, 7, 101]。
  8. i = 7时，nums[7] = 18，直接用18替换101。dp为[2, 3, 7, 101]。

因此，我们得到的最长递增子数组长度为4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for(int i=0;i<nums.size();++i){
            if(dp.empty() || dp[dp.size()-1] < nums[i]){
                dp.push_back(nums[i]);
            }else{
                int index = findFirstBigger(dp, nums[i]);
                dp[index] = nums[i];
            }
        }
        return dp.size();
    }
    int findFirstBigger(vector<int>& dp, int num){
        int index = -1;
        int lo = 0, hi = dp.size()-1;
        while(lo <= hi){
            int mid = (lo + hi) >> 1;
            if(dp[mid] >= num){
                index = mid;
                hi = mid - 1;
            }else{
                lo = mid + 1;
            }
        }
        return index;
    }
};