题解 | #最长递增子序列#

最长递增子序列

http://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481

描述

题目描述

给定数组 arr ，设长度为 n ，输出 arr 的最长递增子序列。（如果有多个答案，请输出其中按数值(注：区别于按单个字符的ASCII码值)进行比较的字典序最小的那个）

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

示例

输入：
[1,2,8,6,4]
返回值：
[1,2,4]
说明：
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）

知识点：动态规划、数组、二分

难度：⭐⭐⭐⭐

题解

方法一：动态规划（超时）

通过动态规划，用dp数组保存数组中每一位为结尾的最长递增子序列长度

如图，由于dp[0]=1, dp[2]=2, dp[3]=3, maxLen = 3

因此在逆向递推收集结果时，满足：

for(int i = n-1, j = maxLen; j > 0; --i) {
    // 根据每一位的LIS长度，从右往左取值
    if(dp[i] == j) {
        lis[--j] = arr[i];
    }
}

算法流程：

通过动态规划思想，先找出状态：以 arr[i] 结尾的子序列
根据 base case 以及选择，通过遍历每个元素，列出状态转移方程：dp[i] = dp[j] + 1;
dp数组保存数组中每一位为结尾的最长递增子序列长度后，在逆向递推收集结果，即根据每一位的LIS长度，从右往左取值

Java 版本代码如下：

import java.util.*;

public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        int n = arr.length;
        // 定义：dp[i]表示以 arr[i] 结尾的最长递增子序列LIS的长度
        int[] dp = new int[n];
        // base case: 以 arr[i] 为结尾的LIS至少包含自己
        Arrays.fill(dp, 1);
        int maxLen = 1;
        // 遍历[1...n]
        for(int i = 1; i < n; i++) {
            // 遍历[0...i-1]
            for(int j = 0; j < i; j++) {
                if(arr[j] < arr[i]) {
                    // 状态转移
                    dp[i] = dp[j] + 1;
                    // arr的最长递增子序列长度
                    maxLen = Math.max(dp[i], maxLen);
                }
            }
        }

        // 保存结果
        int[] lis = new int[maxLen];
        // 遍历maxLen次，收集结果
        for(int i = n-1, j = maxLen; j > 0; --i) {
            // 根据每一位的LIS长度，从右往左取值
            if(dp[i] == j) {
                lis[--j] = arr[i];
            }
        }
        return lis;
    }
}

复杂度分析：

时间复杂度： $O (n^{2})$ ,动态规划的子问题个数为n，每个子问题需要 O(n) 时间进行遍历，因此总的时间复杂度为 O(n^2)

空间复杂度： $O (n)$ ，维护长度为 n 的数组保存状态和结果数组

方法二：贪心+二分

如果完全按照代码区的一步步推算演进，最后会是这样的结果

算法流程：

维护两个数组：tails保存以 arr[i] 元素结尾的最长递增子序列元素，maxLen保存以 arr[i] 元素结尾的最长递增子序列LIS的长度
遍历每个元素，根据两种情况对 tails 和 maxLen 数组进行填充：
- 如果新元素arr[i]大于最右边元素, 则直接添加到数组并更新长度数组
- 如果新元素小于等于tails数组最大(最右边)元素, 则需要在tails数组中寻找第一个大于arr[i]的元素索引firstBigIndex
最后逆向填充结果数组

Java 版本代码如下：

import java.util.*;

public class Solution {
    public int[] LIS (int[] arr) {
        // write code here
        int n = arr.length;
        // 保存以 arr[i] 元素结尾的最长递增子序列元素
        int[] tails = new int[n];
        // 以 arr[i] 元素结尾的最长递增子序列LIS的长度
        int[] maxLen = new int[n];
        tails[0] = arr[0];
        maxLen[0] = 1;
        // tails数组长度
        int tailsLen = 1;
        for(int i = 1; i < n; i++) {
            int num = arr[i];
            // 两种情况
            // 如果新元素arr[i]大于最右边元素, 则直接添加到数组并更新长度数组
            if(num > tails[tailsLen - 1]) {
                tails[tailsLen++] = num;
                maxLen[i] = tailsLen;
            } else {
                // 如果新元素小于等于tails数组最大(最右边)元素,
                // 则需要在tails数组中寻找第一个大于arr[i]的元素索引firstBigIndex
                int lo = 0, hi = tailsLen - 1, firstBigIndex = 0;
                // 二分搜索左边界
                while(lo <= hi) {
                    int mid = lo + ((hi - lo) >> 1);
                    // 向右搜索
                    if(tails[mid] < num) {
                        lo = mid + 1;
                    } else {
                        // 继续向左搜索左边界
                        hi = mid - 1;
                        firstBigIndex = mid;
                    }
                }
                // 替换该位置, 保证最长递增子序列的递增最慢
                tails[firstBigIndex] = num;
                maxLen[i] = firstBigIndex + 1;
            }
        }
        int[] res = new int[tailsLen];
        // 逆向填充
        for(int i = n - 1; i >= 0; --i) {
            if(maxLen[i] == tailsLen) {
                res[tailsLen - 1] = arr[i];
                --tailsLen;
            }
        }
        return res;
    }
}

复杂度分析：

时间复杂度： $O (N l o g N)$ ,要遍历每个元素的复杂度为 O(N)，同时对于两种情况还要进行二分左边界搜索需要 O(logN), 因此总的时间复杂度为 O(NlogN)