LEETCODE 300. 最长上升子序列

LEETCODE 300. 最长上升子序列

题目描述

给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4

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

递归

首先要明白题目的意思,什么叫最长上升子序列
[10,9,2,5,3,7,101,18]为例,[2,3,7]是原数组的子序列,可以看出子序列中没有5,所以子序列并不要求是连续的。
上升意味着数组中第i+1个值必须大于第i个值,所以[5,3,7]就不符合题意了,不是上升子序列。
[2,3,7]虽然是一个上升子序列,但它不是最长的,[2,3,7,101]才是最长的上升子序列,其长度是4。
不过这个值并非唯一,[2,3,7,18]长度也是4,它也是最长的上升子序列,我们并不用求出最长上升子序列这个数组内容,只要输出最大值即可。

我们以10为例,看看以10开头的最长上升子序列是什么?

上图中,我们依次做下面操作:

  1. 910小,不满足上升条件,继续往后查找
  2. 210小,不满足上升条件,继续往后查找
  3. 510小,不满足上升条件,继续往后查找
  4. 310小,不满足上升条件,继续往后查找
  5. 710小,不满足上升条件,继续往后查找
  6. 10110大,满足上升条件,子序列长度+1

[10,101]就是一个上升子序列,由于101后面的18比它小,就没法组队了。
10开头的最长上升子序列就是[10,101]了,当然[10,18]也是。

从上图我们可以知道,从nums[i]为起点,一路找下去直到nums[max],如果i<j并且nums[i]<nums[j],那么[nums[i],nums[j]]就是一个上升子序列。
按照同样的方式处理9和后面的元素,就能找到以9开头,最长的子序列。
处理2和后面的元素,就能找到以2开头,最长的子序列。

但这种思路也不完全对,比如[2,5]是一个上升子序列,[2,3]也是一个上升子序列。但是选择[2,3]肯定比[2,5]更好。
为什么呢?因为35小,[2,3]组队的话,如果后面能碰到一个4,或者5,那么组到一起就是[2,3,4]长度是3,而[2,5]后面就不能再跟上4了,[2,5]后面除非碰到比5大的,否则长度只能是2了。当i<j,并且nums[i]<nums[j]时,其实我们有两种选择

  1. nums[i]nums[j]组成一个子序列,子序列长度+1
  2. nums[i]放弃nums[j],看后面还有没有更好的数字可以组合

对于递归函数来说,就可以这么实现了:

  1. 如果nums[i]>=nums[j],放弃nums[j],继续比较后面的元素
  2. 如果nums[i]<nums[j],将这两个元素组成一个子序列
  3. 如果nums[i]<nums[j],放弃nums[j]继续比较后面的元素

再看下递归函数的执行过程,以[1,2,3,4,5]举例,执行这个数组的递归调用树如下图:

因为树的节点太多了,我没法全部画出来。图中的根节点是f(-1,0),第一个参数是上一个元素的下标位置,第二个参数是当前元素的下标位置,f是函数名。
比如f(0,1)表示下标为0的元素跟下标为1的元素比较,因为满足匹配条件,所以有两条路可以走:

  • 匹配,子序列长度+1,继续比较下标1和下标2的元素,对应图中的f(1,2)
  • 放弃,子序列长度不变,继续比较下标0和下标2的元素,对应图中的f(0,2)

如果是f(11,22)就表示数组下标11的值跟数组下标22的之比较,如果满足上升条件,同样也有两个选择,将f(11,22)+1,然后继续判断f(22,23),或者判断f(11,23)
上图很重要,看明白的话后面的递归函数理解起来就非常容易了,对动态规划的解法理解也有帮助。

下图是[1,5,4,2,3]这个数组最上升子序列的递归调用树(黑色的的部分是触发了递归终止条件,相当于叶子节点)
下图中的左边靠下的f(0,3)意思是:下标为0的1和下标为3的2比较,满足上升条件,所以继续比较下标3和下标4,同时子序列长度+1;或者放弃这个机会,比较下标0和下标4,同时上升子序列长度不变。

注意,递归的解法是无法通过的,因为时间复杂度过高。
动态规划题一般都比较难,其解决思路可能不是那么容易想到,这时候先写出相对容易的递归版本,通过理解递归的运作过程,再推导出动态规划,分两步走理解起来比直接一步到位更容易一些。

java代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null) {
            return 0;
        }
        return dfs(-1,0,nums);
    }
    
    private int dfs(int pre, int cur, int[] nums) {
        if(cur==nums.length) {
            return 0;
        }
        int a = 0;
        int b = 0;
        //pre小于0是初始状态,继续往后判断
        //if条件满足说明是上升子序列,长度要+1
        if(pre<0 || nums[pre]<nums[cur]) {
            a = dfs(cur,cur+1,nums)+1;
        }
        //如果不满足可能是不满足上升子序列条件
        //也可能是 满足条件但主动放弃
        b = dfs(pre,cur+1,nums);
        return Math.max(a,b);
    }
}
                                                         

python代码:

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        N = len(nums)
        def dfs(pre,cur):
            if cur==N:
                return 0
            a,b = 0,0
            # pre小于0是初始状态,继续往后判断
            # if条件满足说明是上升子序列,长度要+1
            if pre<0 or nums[pre]<nums[cur]:
                a = dfs(cur,cur+1)+1
            # 如果不满足可能是不满足上升子序列条件
            # 也可能是 满足条件但主动放弃
            b = dfs(pre,cur+1)
            return max(a,b)
        return dfs(-1,0)
                                                     

递归+记忆化

递归的性能之所以差,因为很多节点做了重复计算。

上图中橙色、红色的节点就被反复计算了好几次。红色节点下面可能还有很多子节点、子子节点,都会有重复计算。如果我们将这些重复的值缓存起来,那么性能就可以大幅度提升(性能不够缓存来凑)。

我们在函数的入口处判断一下相关的参数是否在缓存中,如果在直接返回就可以了,这样后面就省去一大堆重复计算。如果不在缓存中,则需要新计算一遍,再将结果放入缓存中。
注意:python的代码执行仍然会超时。
《算法导论第三版》动态规划的章节中提到过,递归+记忆化的时间复杂度理论上和动态规划是差不多的,但实际执行中时间复杂度上还有常数级别的差异,递归调用本身就需要多耗费一点时间,这就是导致python的递归+记忆化仍然通过不了,而python的动态规划版本可以通过。

java代码:

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null) {
            return 0;
        }
        //因为pre是从-1开始的,所以二维数组的行数需要+1
        int[][] cache = new int[nums.length+1][nums.length];
        for(int[] arr : cache) {
            Arrays.fill(arr,-1);
        }
        return dfs(cache,nums,-1,0);
    }
    
    int dfs(int[][] cache, int[] nums, int pre, int cur) {
        if(cur==nums.length) {
            return 0;
        }
        int a = 0;
        if(cache[pre+1][cur]>-1) {
            return cache[pre+1][cur];
        }
        if(pre<0 || nums[cur]>nums[pre]) {
            a = dfs(cache,nums,cur,cur+1)+1;
        }
        int b = dfs(cache,nums,pre,cur+1);
        cache[pre+1][cur] = Math.max(a,b);
        return cache[pre+1][cur];
    }
}
                                                                  

python代码:

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        N = len(nums)
        # 因为pre是从-1开始的,所以二维数组的行数需要+1		
        cache = [[0 for _ in xrange(N)] for _ in xrange(N+1)]
        def dfs(pre,cur):
            if cur==N:
                return 0
            if cache[pre+1][cur]>0:
                return cache[pre+1][cur]
            a,b = 0,0
            if pre<0 or nums[pre]<nums[cur]:
                a = dfs(cur,cur+1)+1
            b = dfs(pre,cur+1)
            cache[pre+1][cur] = max(a,b)
            return cache[pre+1][cur]
        return dfs(-1,0)
                                                                     

动态规划

下图中上半部分的是递归执行的过程,下半部分是动态规划的执行过程。

递归的执行过程,10跟9,2,5,3,7,101依次比较
动态规划的执行过程,以101为起点,依次跟前面的元素比较,这个过程跟递归正好是相反的。
为什么要反着执行呢?这不是为了耍酷,而是后面的结果需要依赖前面的结果,我们把前面的结果保存下来,后面再计算时,就会依靠前面的结果。
我们来分析一下
首先数组下面那一排数字并不是下标,是动态规划计算出来的临时结果。
10,9,2 这三个元素都递减的,所以到2为止,最长的上升子序列长度为1(因为找不到其他数字可以组队了,最长子序列就是这个数字本身)。
52大,所以到5为止,上升子序列长度为2,这个2是怎么来的呢,他是根据前面计算出的来结果再推算出来的。
同理,到7为止上升子序列长度为3,这个3是根据5下面的那个2推算出来
到101为止,上升子序列长度为4,这个4是根据7下面的那个3推算出来的

于是我们可以得到下面的结论:
假设nums[0..j]这段的最长上升子序列长度为n,如果i>j,并且nums[i]>nums[j],那么nums[0...j..i]这段的最长上升子序列长度为n+1
dp方程就是:

dp[i] = max(dp[i],dp[j]+1)    0<=j<i 且 nums[j]<nums[i]

如果还是不好理解的话,看下面这张图就应该能明白了

数组下面那一排是动态规划计算时用到的数组(以下简称DP数组),它的长度跟元素数组长度一样,所以空间复杂度就是O(N)了,从这里也可以看到动态规划就是用空间换时间。
DP数组初始的时候元素全部置为1
当遍历到元素5时候,因为5的下标大于2,且5>2,那么5对应的dp数组就会这么计算dp[3]=max(dp[3],dp[2]+1)
3的下标大于2的下标,且3>2,所以dp[4]=max(dp[4],dp[2]+1)
7的下标大于5的下标,且7>5,所以dp[5]=max(dp[5],dp[3]+1)
101的下标大于7的下标,且101>7,所以dp[6]=max(dp[6],dp[5]+1)

由于每轮都需要迭代i次,总的时间复杂度就是O(N^2),同时我们会发现,DP数组中最后一个值并非是最终结果。最长的上升子序列长度可能会出现在DP数组中的任意位置,所以我们求一下max(dp)找出最大值再返回就可以了。

java代码:

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null || nums.length==0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        for(int i=0;i<dp.length;++i) {
            dp[i] = 1;
        }
        for(int i=0;i<nums.length;++i) {
            for(int j=0;j<i;++j) { //如果满足上升条件,更新dp数组 if(nums[i]>nums[j]) {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //返回dp数组中的最大值
        return Arrays.stream(dp).max().getAsInt();
    }
}
                                                                                                                                                  

python代码:

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        N = len(nums)
        dp = [1 for _ in xrange(N)]
        for i in xrange(N):
            for j in xrange(i):
                # 如果满足上升条件,更新dp数组
                if nums[j]<nums[i]:
                    dp[i] = max(dp[i],dp[j]+1)
        # 返回dp数组中的最大值
        return max(dp)
                                                                                  

贪心+二分查找

我们之前说过,同样是长度为2的子序列,[2,3]就比[2,5]好。
因为[2,3]后面如果有4的话,组成[2,3,4]长度就是3了,但是[2,5]因为不满足条件,就没法组队了。

我们组成子序列的时候,不仅要让这个序列尽可能的长,而且要让子序列在升的时候尽可能的缓慢[2,3]就比[2,5]上升的缓慢,这样就有机会能拼接出更长的上升子序列。

我们用一个数组来保存当前的最长上升子序列,这个数组是严格递增的。
因为是严格递增的,数组中最后一个值nums[max]就是最大值,如果下次再碰到一个数字n,它比num[max]还要大,那么很明显,这个子序列的长度就要+1,并且将数组n添加到数组的末尾。
假设我们正在遍历数组,已得到的最长上升子序列如下:

[2,3,7,8,11,13,18]是目前为止最长的上升子序列,之后如果又碰到了19,或者101,因为他们都大于数组中的最大值18,所以直接将其添加到数组末尾就可以了,同时子序列的长度要+1。
19101的例子很好理解,但如果下次碰到的数字是6或者12呢?
因为要让子序列上升的尽可能缓慢,那么让[2,5,7...]变成[2,5,6...]更合适,因为后者上升的更缓慢。
同样,将[...8,11,13,18]变成[...8,11,12,18]也是上升的更缓慢一点。
也就是,已知上升子序列[i,i_1,i_2,....,i_n],现在我们在继续遍历的过程中碰到了一个值i_k,这个值是小于i_n的,所以上升子序列的长度还是不变。但是我们需要找到一个位置,将i_k替换掉某个旧的值。
这个替换的方式,用的是二分查找,但跟普通的二分查找稍稍不同,这个查找过程描述如下:

给定一个排序数组和一个目标值,在数组中找到目标值,并将其替换。如果目标值不存在于数组中,找到它将会被按顺序插入的位置i,将其插入位置i

查找过程这里就不详细说了,如果不记得了,可以翻看这篇文章:
搜索插入位置

最长上升子序列的执行过程如下,绿色部分是最长上升子序列数组

java代码:

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null || nums.length==0) {
            return 0;
        }
        //用来保存最长上升子序列的列表arr
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0;i<nums.length;++i) {
            //如果nums[i]比arr的最大值还大,可以组成一个更长的子序列
            //并将其添加到arr末尾			
            if(arr.size()==0 || arr.get(arr.size()-1)<nums[i]) {
                arr.add(nums[i]);
                continue;
            }
            //如果nums[i]比arr最大值小,就要在arr中找查找一个合适的位置,
            //将nums[i]放入,这查找过程是二分查找
            int begin = 0;
            int end = arr.size()-1;
            while(begin<=end) {
                int mid = begin+(end-begin)/2;
                if(arr.get(mid)>nums[i]) {
                    end = mid-1;
                }
                else if(arr.get(mid)<nums[i]) {
                    begin = mid+1;
                }
                else{
                    begin = mid;
                    break;
                }
            }
            arr.set(begin,nums[i]);
        }
        return arr.size();
    }
}
                                                                            

python代码:

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        # 用来保存最长上升子序列的列表arr
        arr = []
        N = len(nums)
        for i in xrange(N):
            # 如果nums[i]比arr的最大值还大,可以组成一个更长的子序列
            # 并将其添加到arr末尾	
            if not arr or nums[i]>arr[-1]:
                arr.append(nums[i])
                continue
            # 如果nums[i]比arr最大值小,就要在arr中找查找一个合适的位置,
            # 将nums[i]放入,这查找过程是二分查找
            begin,end = 0,len(arr)-1
            while begin<=end: mid = begin+(end-begin)/2 if arr[mid]>nums[i]:
                    end = mid-1
                elif arr[mid]<nums[i]:
                    begin = mid+1
                else:
                    begin = mid
                    break
            arr[begin] = nums[i]
        return len(arr)
                                                                            

(全文完)

5 次阅读

发表评论

电子邮件地址不会被公开。