最长上升序列

最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续的的递增序列。

示例 1:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。

示例 2:
输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1

方法一：滑动窗口
滑动窗口中的元素都是连续递增的，最长连续递增序列的长度即为窗口的大小

如果当前元素大于前一个元素，窗口右指针加1
如果当前元素不大于前一个元素，左指针移到到当前位置
在遍历过程中更新最大长度

public int findLengthOfLCIS(int[] nums) {
    if(nums==null||nums.length==0){
        return 0;
    }
    int low=0;
    int ans=1;
    for (int i=1;i<nums.length;i++){
        if(nums[i]<=nums[i-1]){
            low=i;
        }
        ans=Math.max(ans,i-low+1);
    }
    return ans;
}

方法二：动态规划
dp[i]表示以num[i]结尾的连续递增序列的长度(以num[i]为基准，其前面的元素要比它更小)

初始dp[i]=1
如果num[i]>num[i-1] dp[i]=dp[i-1]+1
在遍历过程中用一个遍历记录最长长度

public int findLengthOfLCIS(int[] nums) {
    if(nums==null||nums.length==0){
        return 0;
    }
    int[] dp=new int[nums.length];
    dp[0]=1;
    int ans=1;
    for (int i=1;i<nums.length;i++){
        if(nums[i]>nums[i-1]){
            dp[i]=dp[i-1]+1;
        }  else{
            dp[i]=1;
        }
        ans=Math.max(ans,dp[i]);
    }
    return ans;
}

优化空间复杂度

不需要用一个dp数组，只需要用一个变量记录上一个位置结束的递增长度

public int findLengthOfLCIS(int[] nums) {
    if(nums==null||nums.length==0){
        return 0;
    }
    int ans=1;
    int count=1;
    for (int i=1;i<nums.length;i++){
        if(nums[i]>nums[i-1]){
            count++;
        } else {
            count=1;
        }
        ans=Math.max(ans,count);
    }
    return ans;
}

最长上升子序列

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

示例:

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

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n²) 。

方法一：动态规划
dp[i]表示num[0]...num[i]以num[i]作为最大元素的上升子序列的长度

初始dp[i]=1
dp[i]=max(dp[i],dp[j]) 0<=j<i
在遍历过程中更新最长长度

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

方法二：贪心+二分查找
要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 d[i]（单调递增），表示长度为 i 的最长上升子序列的末尾元素的最小值，用len 记录目前最长上升子序列的长度，起始时 len为 1，d[0] = nums[0]

在遍历过程中，如果nums[i]比d末尾数字大，增加nums[i]加到d中，len++，否则在d中找到大于num[i]的最小元素，将它改为nums[i]

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    int[] d = new int[n];
    int len = 1;
    d[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > d[len - 1]) {
            d[len++] = nums[i];
        } else {
            binaryReplace(d, len, nums[i]);
        }
    }
    return len;
}

private void binaryReplace(int[] d, int len, int num) {
    int low = 0, high = len - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (d[mid] < num) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    d[low] = num;
}

时间复杂度O(nlogn)

搜索插入位置
二分解释

public int searchInsert(int[] nums, int target) {
    // 特殊判断
    if (nums[nums.length - 1] < target) {
        return nums.length;
    }
    // 走到这，一定在[0...n - 1]范围内
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

public int searchInsert(int[] nums, int target) {
    int left= 0, right = nums.length;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] == target){
            return mid;
        } else {
            right = mid;
        }
    }
    return left;
}

public int searchInsert(int[] nums, int target) {
    int left= 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] == target){
            return mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

最长递增子序列的个数

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5

counts[i]表示以i结尾的最长递增序列的种类数
在更新dp的时候：

如果dp[j]+1>dp[i]，说明第一次找到了dp[j]+1长以nums[i]结尾的最长递增序列，此时counts[i]=counts[j]
如果dp[j]+1=dp[i]，说明重复出现了dp[j]+1长以nums[i]结尾的最长递增序列，此时counts[i]+=couns[j]（统计所有重复的个数）

最终再进行一次遍历，如果dp[i]=maxLen，说明当前序列可构成最长递增序列，ans+=counts[i]

public int findNumberOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int[] dp = new int[nums.length];
    int[] counts = new int[nums.length];
    int maxLen = 1;
    Arrays.fill(dp, 1);
    Arrays.fill(counts, 1);
    for (int i = 1; i < nums.length; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    counts[i] = counts[j];
                } else if (dp[j] + 1 == dp[i]) {
                    counts[i] += counts[j];
                }
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    int ans = 0;
    for (int i = 0; i < nums.length; i++) {
        if (dp[i] == maxLen) {
            ans += counts[i];
        }
    }
    return ans;
}