高频面试题总结之最长上升子序列

数据结构
数据结构, 高频面试题总结

题目详情

LintCode No.76

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

最长上升子序列的定义：
最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。

样例
给出 [5,4,1,2,3]，LIS 是 [1,2,3]，返回 3
给出 [4,2,4,5,3,7]，LIS 是 [2,4,5,7]，返回 4

解法1 动态规划

思路：

两个for循环遍历数组：

1
2
3
4
5
6
7
for (int i = 1; i < nums.length; i++) {
           for (int j = 0; j < i; j++) {
               if(nums[i] > nums[j]) {
                   dp[i] = Math.max(dp[j] + 1, dp[i]);
               }
           }
       }

状态转移：
dp[i] = Math.max(dp[j] + 1, dp[i])
时间复杂度：
O(n^2)

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        
        if(nums.length == 0) {
            return 0;
        }
        
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        
        Arrays.sort(dp);
        return dp[nums.length-1];
    }

可以尝试使用二分查找来优化，具体思路如下：

  1. 建个数组，令数组中的每个数的值都为Integer.MAX_VALUE
  2. 从题目所给序列中，依次取出每个值，更新数组
  3. 更新数组的规则为：找到第一个大于取出值的数组元素，替代其值
  4. 最后，从后往前对数组进行遍历，找到第一个非Integer.MAX_VALUE的数组元素的index即为我们所求的结果。

完整代码如下：

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
30
31
32
33
34
35
36
public int longestIncreasingSubsequence(int[] nums) {
        int[] minLast = new int[nums.length + 1];
        minLast[0] = Integer.MIN_VALUE;
        for (int i = 1; i <= nums.length; i++) {
            minLast[i] = Integer.MAX_VALUE;
        }
        
        for (int i = 0; i < nums.length; i++) {
            // find the first number in minLast >= nums[i]
            int index = binarySearch(minLast, nums[i]);
            minLast[index] = nums[i];
        }
        
        for (int i = nums.length; i >= 1; i--) {
            if (minLast[i] != Integer.MAX_VALUE) {
                return i;
            }
        }
        
        return 0;
    }
    
    // find the first number > num
    private int binarySearch(int[] minLast, int num) {
        int start = 0, end = minLast.length - 1;
        while (start <= end) {
            int mid = ((end - start) >> 1) + start;
            if (minLast[mid] < num) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        
        return end + 1;
    }

时间复杂度为O(nlogn)，相比动规，做到了一定程度上的优化。

Compartir Comentarios