leetcode：300. 最长递增子序列

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

输入：nums = [0,1,0,3,2,3]
输出：4

输入：nums = [7,7,7,7,7,7,7]
输出：1

解答 & 代码

解法一：动态规划

动态规划：

动态规划数组 **dp**：dp[i] 代表以 nums[i] 为结尾的最长递增子序列的长度
状态转移方程：**dp[i] = max(dp[j] +1)**，其中 **j < i** 且 **nums[j] < nums[i]**
初始化：dp[0] = 1

而题目要求的最长子序列长度，就是所有 dp[i] 中的最大值

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if(len <= 0)
            return 0;
        vector<int> dp(len, 1);        // 动态规划数组，dp[i] 代表以 nums[i] 为结尾的最长递增子序列的长度
        int maxLen = 0;                // 最长递增子序列长度
        // 状态转移
        for(int i = 0; i < len; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i] && dp[j] + 1 > dp[i])
                    dp[i] = dp[j] + 1;
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

复杂度分析：

时间复杂度
空间复杂度 O(N)：动态规划数组 dp 的空间复杂度 O(N)

执行结果：

执行结果：通过
执行用时：292 ms, 在所有 C++ 提交中击败了 17.36% 的用户
内存消耗：10.2 MB, 在所有 C++ 提交中击败了 58.36% 的用户

解法二：贪心 + 二分查找

如果想让递增子序列尽可能的长，那么贪心的想法就是，每次在上升子序列最后加的那个数的值尽可能小

设置一个 tails 数组， tails[i] 代表长度为 i + 1 的最长上升子序列的末尾元素的最小值

初始时 tails 数组长度 len = 1，tails[0] = nums[0]
可以证明：tails 数组是单调递增的，即对于 i>j，有 tails[i] > tails[j]

算法流程：
依次遍历 nums 数组中的每个元素，假设当前遍历到 nums[i]：

如果 nums[i] > tails[len-1]，说明上升子序列的长度可以加一，将 nums[i] 压入 tails 数组尾部，tails 数组的长度 len 加一
否则，找到 tails[pos] < nums[i] < tails[pos+1] 的位置 pos，用 nums[i] 来更新 tails[pos+1]，说明长度为 pos+2 的上升子序列的末尾元素可以有更小的值(即 nums[i])
- 因为 tails 数组是单调递增的，因此可以用二分查找来降低时间复杂度，也就是要查找 tails 数组中大于等于 nums[i] 的左边界 leftBoundary，用 nums[i] 来更新 tails[leftBoundary]

返回最终 tails 数组的长度 len，就是 nums 数组的最长递增子序列长度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if(len <= 0)
            return 0;
        vector<int> tails = {nums[0]};
        for(int i = 1; i < len; ++i)
        {
            if(nums[i] > tails.back())
                tails.push_back(nums[i]);
            else if(nums[i] < tails.back())
            {
                int target = nums[i];
                int left = 0;
                int right = tails.size() - 1;
                int leftBoudary = right;
                while(left <= right)
                {
                    int mid = left + (right - left) / 2;
                    if(tails[mid] >= target)
                    {
                        leftBoudary = mid;
                        right = mid - 1;
                    }
                    else
                        left = mid + 1;
                }
                tails[leftBoudary] = target;
            }
        }
        return tails.size();
    }
};

复杂度分析：

时间复杂度 O(NlogN)：外循环遍历 nums 数组时间复杂度 O(N)，二分查找时间复杂度 O(log N)
空间复杂度 O(N)：

执行结果：通过
执行用时：4 ms, 在所有 C++ 提交中击败了 98.40% 的用户
内存消耗：10 MB, 在所有 C++ 提交中击败了 95.31% 的用户

拓展题

[困难] 354. 俄罗斯套娃信封问题

hot 100

[中等] 300. 最长递增子序列

题目

解答 & 代码

解法一：动态规划

解法二：贪心 + 二分查找

拓展题