面试热题（最长上升子序列）

朴灿烈づ我的快乐病毒、 2023-10-14 15:45 21阅读 0赞

> 给你一个整数数组 `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 。

![133b7fe9b88142bcb344196f2688aee1.png][]

由上图我们可以很容易直到该数组中的最长递增子序列的长度为4，可是计算机可不知道这么算，所以我们要告诉它得这么算，我们仔细找找规律

![85225befc49a483d8d52c7fde603113d.png][]

这种的分析是不是能让你看出一点点规律，如果当前值i比i-1前的最长自序列的最后一个值大时，将当前这个值加入这个递增子序列中，是不是我们就比较容易得到：

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

那么我们动态规划中最难的一步已经写出来了，状态转移方程，接下来就是动规的一般解题步骤，入参判断，维护一个dp数组，对其进行初始化，具体的看下面的源代码：

public int lengthOfLIS(int[] nums) {
          if(nums==null||nums.length==0){
              return 0;
          }
          int[] dp=new int[nums.length];
          Arrays.fill(dp,1);
            for (int i = 1; i <nums.length; i++) {
                for (int j = 0; j <i; j++) {
                    if(nums[j]<nums[i]){
                  dp[i]=Math.max(dp[j]+1,dp[i]); 
                    }
                    
                }
            }
           return Arrays.stream(dp).max().getAsInt();
        }

在大家再给大家介绍一种解法，面试时两种解法任选一种即可，我认为还是动态规划这种比较容易好记

堆纸牌方法：

这种方法一般人还真想不到，可能那种久经牌场的人说不定可以想到：

![668a60fe1b9f48e1ab4863ade42d0a64.png][]

类似于蜘蛛纸牌一样的游戏规则，每次找到最左边的适合当前牌的牌堆，如果没有就直接新创一个牌堆

![4d6d355badb643079b100b363b31827a.png][]

没堆牌出一张组成子序列，牌堆的堆数越多，最长子序列的长度也就越大：

【5，6，7，J】、【5，7，8，J】...

所以我们应该怎么样去模拟这个算法呢？

由于我们要时刻的知道每堆牌的顶牌，所以我们可以维护一个数组去记录每个堆的牌顶

int[] top=new int[nums.length];
    int count=0;//一开始，未进行发牌，牌堆数为0

![299e6e741496e559e3d828a03eef2e48.jpeg][]

如果有这么sexy的荷官给你发牌，你做题怎么可能会错？比如邱淑贞姐姐给你发牌，哒哒哒...

![094845958ae64523b1e963c3f87e877d.png][]

![a1c854ca7d0c43fa8a015499b83f5a9e.png][]

因为数组中的索引是从0开始的，但是牌堆数确实从1开始的，所以当我们查找可以放当前牌的最左牌堆的索引等于牌堆数的时候，就应该重新创建一个牌堆，如果不太了解二分搜索最左侧搜索，请看[二分搜索篇][Link 1]

public int lengthOfLIS(int[] nums) {
          if(nums==null||nums.length==0){
              return 0;
          }
          int[] top=new int[nums.length];
          int count=0;
          //进行发牌
          for(int num:nums){
    
              int left=0;
              int right=count;
      //这里给大家说明以下，这种二分查找区间的时候区间是左闭右开的
      //因为count代表的是堆数(从1开始)，但是right指针代表的是数组的索引(从0开始)，指针永远不可能到达堆数的数量
              while(left<right){
                  int mid=left+(right-left)/2;
                  if(top[mid]>=num){
                      right=mid;//不断的去优先收缩右区间
                  }else{
                      left=mid+1;//收缩左区间
                  }
              }
    
              //找到最小的大于等于num的索引大小
              if(left==count){
                  count++;
              }
              //更新牌顶元素
              top[left]=num;
          }
          return count;
        }

[133b7fe9b88142bcb344196f2688aee1.png]: https://img-blog.csdnimg.cn/133b7fe9b88142bcb344196f2688aee1.png
[85225befc49a483d8d52c7fde603113d.png]: https://img-blog.csdnimg.cn/85225befc49a483d8d52c7fde603113d.png
[668a60fe1b9f48e1ab4863ade42d0a64.png]: https://img-blog.csdnimg.cn/668a60fe1b9f48e1ab4863ade42d0a64.png
[4d6d355badb643079b100b363b31827a.png]: https://img-blog.csdnimg.cn/4d6d355badb643079b100b363b31827a.png
[299e6e741496e559e3d828a03eef2e48.jpeg]: https://img-blog.csdnimg.cn/img_convert/299e6e741496e559e3d828a03eef2e48.jpeg
[094845958ae64523b1e963c3f87e877d.png]: https://img-blog.csdnimg.cn/094845958ae64523b1e963c3f87e877d.png
[a1c854ca7d0c43fa8a015499b83f5a9e.png]: https://img-blog.csdnimg.cn/a1c854ca7d0c43fa8a015499b83f5a9e.png
[Link 1]: https://blog.csdn.net/dfdbb6b/article/details/132021061?spm=1001.2014.3001.5501