最长递增子序列

题目介绍

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

方法一：暴力搜（会超时）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        return dfs(nums, -1, Integer.MIN_VALUE, 0);
    }

    int dfs(int[] nums, int i, int pre, int len) {
        if (i == nums.length-1) return len;
        int ans = len;
        for (int j = i+1; j < nums.length; j++) {
            if (i == -1 || nums[j] > nums[i]) {
                ans = Math.max(ans, dfs(nums, j, nums[j], len+1));
            }
        }
        return ans;
    }
}

方法二：动态规划

定义dp[i]为考虑前i个元素，以第i个数字结尾的最长上升子序列的长度。那么状态转移方程是这样的：

1
2
3
4
5
6
7
for (int j = 0; j < i; j++) {
    if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[j]+1, dp[i]);
    }
}
//如果所有的nums[j]都比nums[i]小，那么应该为1
dp[i] = Math.max(1, dp[i]);

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
            //如果所有的nums[j]都比nums[i]小，那么应该为1
            dp[i] = Math.max(1, dp[i]);
        }
        
        return Arrays.stream(dp).max().orElse(1);
    }
}

方法三：贪心+二分

思路如下：

  1. 创建一个数组seq，用于存储当前的递增子序列。
  2. 遍历给定的 nums 中的每个元素num。
  3. 在数组seq中使用 lowerBound 函数找到第一个大于或等于 i 的元素的位置loc。
  4. 如果loc等于数组seq的结束位置（即没有找到大于或等于 i 的元素），则将num加入到数组seq的末尾。
  5. 否则，将数组seq中位置loc的元素替换为num，以保持数组seq仍然是递增的。
  6. 最后返回数组seq的大小，即最长递增子序列的长度。

此方法的难点在于 lowerBound 函数的实现，它和传统的二分查找还有区别。对于传统二分查找，找到元素就可以直接返回，不需要确定整个区间，但是对于 lowerBound 函数，找到相等的元素并不能直接返回，因为有可能前面还有重复的元素，所以需要把整个区间都确定了才可以。

对于区间[l,r]（双闭区间，表示待涂色的区间），我们可以定义这样一个循环不变量：l左边的元素（不包括l）为红色，代表小于target，表示不满足要求；r右边的元素为绿色，代表大于等于target，表示满足要求。当区间所有元素的颜色都确定的时候，我们只需要返回l就可以了。

那如果没有一个元素比target大会怎么办呢？l会一直右移，直到l的值为seq.size()，退出循环。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        List<Integer> seq = new ArrayList<Integer>(n);
        for (int num : nums) {
            int loc = lowerBound(seq, num);
            if (loc == seq.size()) {
                seq.add(num);
            } else {
                seq.set(loc, num);
            }
        }
        return seq.size();
    }

    private int lowerBound(List<Integer> seq, int target) {
        int l = 0, r = seq.size()-1;
        // 如果所有数都比target要小的话，l会一直向右移动，一直到seq.size()这个位置
        while (l <= r) { // 区间不为空
            int mid = (l+r)/2;
            if (seq.get(mid) < target) {
                l = mid+1;
            } else {
                r = mid-1;
            }
        }
        return l;
    }
}