Tag Archives: LIS

LeetCode Longest Increasing Subsequence

300. Longest Increasing Subsequence

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

Example:

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?


给定一个数组,求最长上升子序列(Longest Increasing Subsequence, LIS)的长度。子序列可以是不连续的,和子串不一样。
此题有两种解法,一种$O(n^2)$,另一种$O(nlgn)$。
先来看$O(n^2)$。设length[i]表示到nums[i]时的LIS,那么此时已知了length[0,…,i-1],对于$j\in[0,…,i-1]$,如果nums[i]>nums[j],则在i处的LIS至少是length[j]+1,因为可以在nums[j]后面接nums[i],构成LIS,所以在i处的LIS加一。我们尝试所有的$j\in[0,…,i-1]$,找一个最大的length[j]+1赋给length[i]。
递推式如下:

length(i) =  max  { length(j) + 1 : if nums[j] < nums[i] }
           0≤j≤i-1

这种思路的代码如下,因为需要两层循环,所以时间复杂度为$O(n^2)$。

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

本代码提交AC,用时33MS。
接下来看看$O(nlgn)$的解法。
对于数组d(代码中的数组nums的简称),我们定义一个辅助数组B,B[j]保存了到目前为止LIS=j时的最后一个数的最小的数,比如B[3]=8表示到目前为止长度为3的上升子序列的最后一个数的最小值为8。我们不断更新B的长度和数值,最后B的长度就是最长的上升子序列的长度,但是数组B并不是一个LIS。
举例说明。假设数组下标从1开始。数组d=[3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12],初始时B的长度为1,且B[1]=3表明此时最长上升子序列的长度为1,且该LIS的最后一个数的最小值是3。
d[2]=5,因为d[2]>B[1],所以5可以加入最长上升子序列,导致此时的最长上升子序列长度为2,且最后一个数的最小值就是5,所以B[2]=5。此时B[1]=3不变,因为长度为1的LIS的末尾数值还是3不变。B=[3,5]
d[3]=6,同上,d[3]>B[2],所以6也加入最长上升子序列,导致LIS=3,且B[3]=6B=[3,5,6]
d[4]=2,注意此时d[4]<B[3],所以2不能增加以B[3]=6结尾的最长上升子序列,所以数组B的长度不变。查找B,发现2比B[1]=3小,所以替换B[1]=3为B[1]=2,此含义为长度为1的LIS的末尾最小数由3变更为2。这很好理解,因为2自身可以作为一个LIS,且比3自身作为LIS要小。B=[2,5,6]
d[5]=5,同上,d[5]<B[3],查找B,更新B[2]=5,因为B[2]本身就是5,所以更新前后一样。B=[2,5,6]
d[6]=4,d[6]<B[3],无法增长最长上升子序列,查找B,发现4在B[1]=2和B[3]=6之间,更新B[2]=4,含义为长度为2的LIS的最后一个数的最小值由5更新为4。B=[2,4,6]。其实这样更新的目的就是为了把各个长度的LIS的末尾的最小数变小,使得后续的数更有可能接在之前LIS的末尾来增加LIS的长度。
d[7]=19,d[7]>B[3],贡献LIS长度,直接加入数组B,即B[4]=19B=[2,4,6,19]
d[8]=5,查找B,在4,19之间,所以更新B[3]=5B=[2,4,5,19]
d[9]=6,查找B,更新B[4]=6B=[2,4,5,6]
d[10]=7,d[10]>B[4],贡献LIS长度,直接加入数组B,即B[5]=7B=[2,4,5,6,7]
d[11]=12,d[11]>B[5],贡献LIS长度,直接加入数组B,即B[6]=12B=[2,4,5,6,7,12]
以上算法过程涉及到在数组B中查找当前元素d[i]的替换位置,因为数组B是有序的,所以可以使用二分查找,最终算法的时间复杂度降为了O(nlgn)。
STL中自带了在有序数组中二分查找的函数,lower_bound输入为一个数组B和目标target,返回数组B中不小于target的最小下标。我们也可以自己用二分查找实现。
这种思路的代码如下:

class Solution {
public:
    int lowerbound(vector<int>& B, int target)
    {
        int l = 0, r = B.size() – 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (B[m] == target)
                return m;
            else if (B[m] > target)
                r = m – 1;
            else
                l = m + 1;
        }
        return B[l] < target ? (l + 1) : l;
    }
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        if (n < 1)
            return 0;
        vector<int> B = { nums[0] };
        for (int i = 1; i < n; ++i) {
            if (nums[i] > B.back())
                B.push_back(nums[i]);
            else {
                //*lower_bound(B.begin(), B.end(), nums[i]) = nums[i];
                B[lowerbound(B, nums[i])] = nums[i];
            }
        }
        return B.size();
    }
};

本代码提交AC,用时3MS,速度一下提高了不少。
参考:

二刷。第二种解法,可以直接调stl的lower_bound,最好自己写,和 http://code.bitjoy.net/2020/03/21/leetcode-find-first-and-last-position-of-element-in-sorted-array/ 这题代码FindFirstIndex一致,记住二分搜索的标准写法。

class Solution {
public:
	int lengthOfLIS(vector<int>& nums) {
		int n = nums.size();
		if (n == 0)return 0;

		vector<int> curmin;
		for (int i = 0; i < n; ++i) {
			if (curmin.empty() || nums[i] > curmin.back()) {
				curmin.push_back(nums[i]);
			}
			else {

				//vector<int>::iterator it = lower_bound(curmin.begin(), curmin.end(), nums[i]);
				//*it = nums[i];

				int l = 0, r = curmin.size() - 1;
				while (l <= r) {
					int m = l + (r - l) / 2;
					if (nums[i] <= curmin[m]) {
						r = m - 1;
					}
					else {
						l = m + 1;
					}
				}
				curmin[r + 1] = nums[i];


			}
		}
		return curmin.size();
	}
};

本代码提交AC,用时8MS。

LeetCode Increasing Triplet Subsequence

334. Increasing Triplet Subsequence334. Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1] Output: false

问一个数组中是否有严格递增的三个数存在。
解法:令a是当前最小值,b是比a大的最小值,如果某个nums[i]>b,则a,b,nums[i]构成严格递增的三个数。
因为a,b是最小的递增二元组,如果连这样都没找到递增序列,则不可能有递增三元组了。
完整代码如下,需要注意数组中可能有相同元素,所以第一个if要用<=。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums)
    {
        int a = INT_MAX, b = INT_MAX;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] <= a) {
                // 必须<=
                a = nums[i];
            }
            else if (nums[i] < b) { // <或<=
                b = nums[i];
            }
            if (nums[i] > b) // 必须>
                return true;
        }
        return false;
    }
};

本代码提交AC,用时9MS。
二刷。首先想到了最长上升子序列,求到LIS,如果长度大于等于3的话,则肯定存在上升的3元组。代码如下:

class Solution {
private:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        if (n < 1)
            return 0;
        vector<int> B = { nums[0] };
        for (int i = 1; i < n; ++i) {
            if (nums[i] > B.back())
                B.push_back(nums[i]);
            else {
                *lower_bound(B.begin(), B.end(), nums[i]) = nums[i];
            }
        }
        return B.size();
    }
public:
    bool increasingTriplet(vector<int>& nums) { return lengthOfLIS(nums) >= 3; }
};

本代码提交AC,用时6MS。