300. 最长递增子序列

今天药忘吃喽~ 2024-04-01 09:36 63阅读 0赞

问题描述：

> 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。  
> 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\] 是数组 \[0,3,1,6,2,2,7\] 的子序列。

问题思路：

思路一：运用动态规划的思想，维护一个数组dp，dp\[i\]的含义是：一直到第i个元素，严格递增子序列的最大长度。  
dp\[i\] = max\{dp\[j\]\} + 1，其中j < i  
遍历到第i个元素时，把前面的所有元素k1,k2,k3都比较一下，如果可以凑成递增子序列，则取dp\[k1\],dp\[k2\],dp\[k3\]中最大值，然后 +1，就是到i元素目前的最长子序列长度。

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
    
            // 最长递增子串长度
            int maxList = 1;
    
            int[] dp = new int[nums.length];
            // 迭代数组
            for (int i = 0; i < nums.length; i++) {
        
    
                int max = 1;
                // 每次循环都和前面的所有数比较， 判断能否形成递增，记录max{dp[j]}
                for (int j = 0; j < i; j++) {
        
                    // 如果大于，则符合递增
                    if(nums[i] > nums[j]){
        
                        max = Math.max(dp[j] + 1, max);
                    }
                }
                dp[i] = max;
                maxList = Math.max(maxList, max);
            }
            return maxList;
    
        }
    }

时间复杂度 O( n 2 n^\{2\} n2)  
空间复杂度O(n)  
思路二：动态规划+二分查找  
降低时间复杂度， 解法一中，遍历计算 dp 列表需 O(N)，计算每个 dp\[k\]需 O(N)O(N)。

1.  动态规划中，通过线性遍历来计算 dp 的复杂度无法降低；
2.  每轮计算中，需要通过线性遍历 \[0,k) 区间元素来得到 dp\[k\]，可以考虑维护一个有序的数组来用二分查找，使得复杂度降低。

思路：新建数组 tail，用于保存最长上升子序列。tail中存储最长子串的尾数。对原序列进行遍历，将每位元素二分插入 tail 中。  
**如果 tail 中元素都比它小，将它插到最后。**  
因为都比它小，如果要形成最小子串，它只能放在最后才能满足。

**否则，用它覆盖掉比它大的元素中最小的那个。**  
第一个比它小的数，覆盖它有助于后面再续更多的子串。而且是第一个，所以前面的肯定比它小，后面的也肯定比它大，不会影响子串的结构。  
总之，思想就是让 tail 中存储比较小的元素。这样，tail 未必是真实的最长上升子序列，但长度是对的。

比如： 数组 78912

> tail数组： 迭代到7 \[7\]  
> 迭代到8 比较tail中，发现都比8小，直接插入到最后 \[7,8\]  
> 迭代到9 比较tail中，发现都比9小，直接插入到最后 \[7,8,9\]  
> 迭代到1 比较tail中，找到第一个比1大的数，覆盖 \[1,8,9\]  
> 迭代到2 比较tail中，找到第一个比2大的数，覆盖 \[1,2,9\]

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
    
            if(nums.length == 0){
        
                return 0;
            }
            /**
    
            定义一个最长递增子序列数组tail[i],表示i长的递增子序列的尾数为tail[i]
            每次遍历时，找到第一个大于x[i]的数，然后替换它。二分查找实现
            如果没有则，放在最后tail[i] = x[i]
             */ 
            int[] tail = new int[nums.length];
            tail[0] = nums[0];
            // tail数组中存储的数据长度
            int res=1;
            
            for(int i=1;i<nums.length;i++){
        
                // 如果x[i]大于tail中所有元素，直接放在最后即可
               if(nums[i] > tail[res-1]){
        
                   tail[res++] = nums[i];
               }else if(nums[i] == tail[res-1]){
        
                   continue;
               }else{
        
                   int index = findFirst(tail,nums[i],res-1);
                   if(index>0){
        
                       if(tail[index-1] < nums[i]){
        
                          tail[index] = nums[i];
                       }
                   }else{
        
                       tail[index] = nums[i];
                   }
                   
               }
            } 
            return res; 
        }
        private int findFirst(int[] nums, int x,int right){
        
            // 找到第一个大于x的数 if(nums[k]>x) 包含
            int left=0;
            int mid;
            while(left<right){
        
                mid = (left+right)/2;
                if(nums[mid]>x){
        
                    right=mid;
                }else{
        
                    left=mid+1;
                }
            }
            return left;
        }
    }

![在这里插入图片描述][400744e557ac4301a475d40223fe49e7.png]

再附上一个找最后一个比它小的元素，覆盖后一位数的算法

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
    
            if(nums.length == 0){
        
                return 0;
            }
            /**
    
            定义一个最长递增子序列数组tail[i],表示i长的递增子序列的尾数为tail[i]
            每次遍历时，找到最后一个小于x[i]的数，然后替换它后一位。二分查找实现
            如果没有则，放在最后tail[i] = x[i]
             */ 
            int[] tail = new int[nums.length];
            tail[0] = nums[0];
            // tail数组中存储的数据长度
            int res=1;
        
            for(int i=1;i<nums.length;i++){
        
                // 如果x[i]大于tail中所有元素，直接放在最后即可
               if(nums[i] > tail[res-1]){
        
                   tail[res++] = nums[i];
               }else if(nums[i] == tail[res-1]){
        
                   continue;
               }else{
        
                   int index = findFirst(tail,nums[i],res-1);
                   tail[index+1] = nums[i];
               }
            } 
            return res; 
        }
        private int findFirst(int[] nums, int x,int right){
        
            // 找到最后一个小于x的数 if(nums[k]<x) 包含
            // 由于可能找不到，所以left=-1
            int left=-1;
            int mid;
            while(left<right){
        
                mid = (left+right+1)/2;
                if(nums[mid]<x){
        
                    left=mid;
                }else{
        
                    right=mid-1;
                }
            }
            return left;
        }
    }

[400744e557ac4301a475d40223fe49e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5fa2a858f1d3455eaec64265a6f9550c.png