题目描述

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1 – O(n^2)

这是一道经典的dp题目,大体上有两种解法,第一种是dp(时间复杂度O(n^2));第二种是dp+二分搜索(时间复杂度O(nlogn)),我们先介绍O(n^2)的解法。而第一种dp还可以分为Bottom-up和Top-down两种实现方式。

Bottom-up

我们定义数组dp[|nums|],dp[i]表示使用nums数组前i个元素且必须使用nums[i],能够构成的最长递增子序列的长度。那么有dp[i] = max(dp[j]) + 1, 其中nums[i] > nums[j], j < i,如果找不到这样的j,那么dp[i] = 1。

如果形象的描述算法的执行过程那就是使用双重循环,外循环使用变量i指向nums数组的每个元素,然后内循环用变量j扫描0~i。当nums[i] > nums[j]时,更新prev = max(prev, dp[j])。当内层循环扫描完毕,更新dp[i] = perv + 1。当双重循环执行完毕,dp数组中的最大值就是nums的最长递增子序列。

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0)
            return 0;
        int ans = 1;
        int[] dp = new int[nums.length];
        dp[0] = 1;

        for (int i = 1; i < nums.length; i++) {
            int prev = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    prev = Math.max(prev, dp[j]);
                }
            }
            dp[i] = prev + 1;
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

Top-down

自顶向下的思路使用递归来实现,我们定义一个辅助函数LIS(nums, curr),表示从nums数组的前curr个元素(包含curr)寻找LIS,并返回LIS的长度。那么我们需要利用更小的子问题求解当前问题,所以在for循环中又递归调用LIS。

 private int LIS(int[] nums, int curr) {
    if (cache[curr] > 0)
        return cache[curr];
    int currLIS = 1;
    for (int i = 0; i < curr; i++) {
        if (nums[i] < nums[curr]) {
            currLIS = Math.max(currLIS, LIS(nums, i) + 1);
        }
    }
    cache[curr] = currLIS;
    return currLIS;
}

为了避免重复求解,我们使用数组int[] cache记录求解过问题的答案。现在我们只需要循环的调用LIS函数,将各种问题的规模都交给LIS函数来求解,最大值就是数组nums的LIS。

for (int i = 0; i < nums.length; i++) {
    ans = Math.max(ans, LIS(nums, i));
}

全部代码如下:

class Solution {
    private int[] cache;

    public int lengthOfLIS(int[] nums) {
        int ans = 0;
        cache = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans = Math.max(ans, LIS(nums, i));
        }
        return ans;
    }

    private int LIS(int[] nums, int curr) {
        if (cache[curr] > 0)
            return cache[curr];
        int currLIS = 1;
        for (int i = 0; i < curr; i++) {
            if (nums[i] < nums[curr]) {
                currLIS = Math.max(currLIS, LIS(nums, i) + 1);
            }
        }
        cache[curr] = currLIS;
        return currLIS;
    }
}

解法2 – O(nlogn)

解法2是一个神奇的解法,我们一边读取nums数组,一边维护一个由nums形成的递增子序列 – dp。当扫描完nums数组后,有序数组dp填充截止位置的就是LIS。因为dp数组是有序的,我们可以使用二分查找,搜索当前元素nums[i]在dp中的插入位置。

例如给定数组nums=[10,9,2,5,3,7,101,18],
i = 0, dp = [10, 0, 0, 0, 0, 0, 0, 0]
i = 1, dp = [9, 0, 0, 0, 0, 0, 0, 0]
i = 2, dp = [2, 0, 0, 0, 0, 0, 0, 0]
i = 3, dp = [2, 5, 0, 0, 0, 0, 0, 0]
i = 4, dp = [2, 3, 0, 0, 0, 0, 0, 0]
i = 5, dp = [2, 3, 7, 0, 0, 0, 0, 0]
i = 6, dp = [2, 3, 7, 101, 0, 0, 0, 0]
i = 7, dp = [2, 3, 7, 18, 0, 0, 0, 0]

在实现时,我们使用Java提供的idx = Arrays.binarySearch(nums, start, end, target)。如果能够找到target,则返回它的索引;如果找不到target,将会返回idx = -(插入位置 – 1),这是一个负数。如果idx < 0,说明没有那个元素,我们将返回的负数逆运算,得到插入位置 = -(idx + 1),在那个位置上填入当前元素;如果idx >= 0,我们在那个位置插入nums[i]使得dp数组保持有序。

index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) – 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

JDK文档 – 关于Arrays.binarySearch的返回值

在扫描nums数组时,有一些元素插入到dp中(例子中i=3 -> i=4),有一些元素将dp数组中的元素替换(例子中i=5 -> i=6)。总的来看,dp数组的长度是不断增加的。只有当Arrays.binarySearch返回的插入位置和dp数组填充截止位置相等时,我们才应该增加LIS的长度。当整个nums数组扫描完毕,那么dp数组填充的截止位置就是LIS的长度。

每一次扫描nums中的元素都会调用二分搜索,因此时间复杂度为O(nlogn)。全部代码如下:

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int idx = Arrays.binarySearch(dp, 0, len, num);
            if (idx < 0)
                idx = -(idx + 1);
            dp[idx] = num;
            if (len == idx)
                len++;
        }
        return len;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *