leetcode 链接：最长递增子序列

题目

给你一个整数数组 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] 代表以第 i 个元素为结尾的最长上升子序列长度（子序列必须包含 nums[i]
• 状态转移方程：
• dp 数组的最大值就是 nums 数组的最长递增子序列长度

时间复杂度 O()，空间复杂度 O(N)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int size = nums.size();
        if(size <= 1)        // 特殊情况：如果数组为空则返回0；如果只有一个元素则返回 1
            return size;

        // 动态规划
        vector<int> dp(size, 1);    // dp[i] 代表以第i个元素为结尾的最长上升子序列长度（子序列必须包含nums[i]）
        for(int i = 0; i < size; ++ i)    // 从左到右遍历数组，计算 dp 数组的值
        {
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i] && dp[j] + 1 > dp[i])
                    dp[i] = dp[j] + 1;
            }
        }

        // dp 数组中的最大值就是 nums 数组的最长递增子序列长度
        int maxLen = 0;
        for(int i = 0; i < size; ++i)
        {
            if(dp[i] > maxLen)
                maxLen = dp[i];
        }
        return maxLen;
    }
};

执行结果：

执行结果：通过

执行用时：332 ms, 在所有 C++ 提交中击败了 59.22% 的用户
内存消耗：10.2 MB, 在所有 C++ 提交中击败了 70.98% 的用户

解法二：贪心 + 二分查找

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

设置一个 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 数组的长度 len，就是 nums 数组的最长递增子序列长度

空间复杂度 O(N)，时间复杂度 O(NlogN)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int size = nums.size();
        if(size <= 0)    // 特殊情况
            return 0;

        // 贪心
        // tails[i] 代表长度为 i + 1 的最长上升子序列的末尾元素的最小值
        vector<int> tails(1, nums[0]);        // 初始时 tails[0] = nums[0]
        // 遍历数组 nums
        for(int i = 1; i < size; ++i)
        {
            // 如果 nums[i] > tails[len-1]，则在 tails 末尾插入 nums[i]
            if(nums[i] > tails.back())
                tails.push_back(nums[i]);
            // 否则，二分查找tails数组中满足 tails[pos] < nums[i] < tails[pos+1]的位置pos
            else if(nums[i] < tails.back())
            {
                int pos = -1;   // tails 中比 nums[i] 小的最大元素位置
                int left = 0;
                int right = tails.size() - 1;
                while(left <= right)
                {
                    int mid = left + (right - left) / 2;
                    if(tails[mid] < nums[i])
                    {
                        pos = mid;
                        left = mid + 1;
                    }
                    else
                        right = mid - 1;
                }
                // 用 nums[i] 来更新 tails[pos+1]，即更新长为 pos+2 的最长上升子序列的末尾元素的最小值
                tails[pos + 1] = nums[i];
            }
        }
        // 最后 tails 数组的长度就是答案
        return tails.size();
    }
};

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 93.33% 的用户
内存消耗：10.1 MB, 在所有 C++ 提交中击败了 90.21% 的用户

进阶：要求输出按数值字典序最小的最长递增子序列

牛客网链接：NC91 最长递增子序列

分为两个步骤：

1. 求得以数组 arr 每个位置为结尾的最长递增子序列的长度，存储在 maxLen 数组中
   1. 可以用 动态规划 做，求得的 dp 数组就是 maxLen
   2. 也可以用 贪心+二分查找 做，需要额外增加一个 maxLen 数组
2. 倒序遍历 maxLen，如果当前的 maxLen[i] == 剩余的最长递增子序列的长度 j，--j，result[j] = arr[i]

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        int size = arr.size();
        if(size <= 0)
            return vector<int>{};

        // 第一步：贪心+二分查找
        // 求得以数组 arr 每个位置为结尾的最长递增子序列的长度，存储在 maxLen 数组中
        vector<int> tails(1, arr[0]);
        vector<int> maxLen(size, 1);
        for(int i = 1; i < size; ++i)
        {
            if(arr[i] > tails.back())
            {
                tails.push_back(arr[i]);
                maxLen[i] = tails.size();
            }
            else
            {
                int left = 0;
                int right = tails.size() - 1;
                int pos = -1;
                while(left <= right)
                {
                    int mid = left + (right - left) / 2;
                    if(tails[mid] < arr[i])
                    {
                        pos = mid;
                        left = mid + 1;
                    }
                    else
                        right = mid - 1;
                }
                tails[pos + 1] = arr[i];
                maxLen[i] = pos + 2;
            }
        }

        // 第二步：得到按字典序最小的最长递增子序列
        vector<int> result(tails.size(), 0);
        for(int i = size - 1, j = tails.size(); j > 0; --i)
        {
            if(maxLen[i] == j)
            {
                --j;
                result[j] = arr[i];
            }
        }
        return result;
    }
};

执行结果：通过

执行用时：31 ms, 在所有 C++ 提交中击败了 98.29% 的用户
内存消耗：4188 KB, 在所有 C++ 提交中击败了 56.66% 的用户