GuilinDev

Lc0300

05 August 2008

300 Longest Increasing Subsequence

原题概述

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

text Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

题意和分析

这是经典题，如果采取暴力法来解复杂度得是排列组合的阶乘级。求最优解一般可以用动态规划，这是动态规划中的区间型题目，

首先状态定义，dp[i]表示数组中第i个元素为止该位置的最长子序列长度（从0开始），那么dp[i+1]就是在i后面多一个元素的情况下，如果nums[i] < nums[i+1] (表示在i+1这个位置上，最长子序列的长度有可能会有更长的情况了)，那么这时候检查dp[i+1]是否小于dp[i]+1（表示在i+1这个位置上，最长子序列的长度出现更长的情况了，这时候更新i+1位置dp[i+1]的值），否则不动，最后找出各个位置最大的子序列的数值，时间复杂度，用递推，外面套一层循环表示每个元素都计算下，里面套一个循环表示在外层元素的基础上，根据递推公式和之前保存的值，计算最长子序列，所以为O(n^2)。

1) DP

  1. 定义状态 由于一个子序列一定会以一个数结尾，于是将状态定义成：dp[i] 表示以 nums[i] 结尾的「上升子序列」的长度。注意：这个定义中 nums[i] 必须被选取，且必须是这个子序列的最后一个元素。

  2. 考虑状态转移方程

    • 遍历到 nums[i] 时，需要把下标 i 之前的所有的数都看一遍；
    • 只要 nums[i] 严格大于在它位置之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列；
    • dp[i] 就等于下标 i 之前严格小于 nums[i] 的状态值的最大者 +1， 也就是下标 i 之前严格小于 nums[i] 的所有状态值中的最大者 + 1。
  3. 初始化 - dp[i] = 1，1 个字符显然是长度为 1 的上升子序列。
  4. 输出
    • 这里要注意，不能返回最后一个状态值；
    • 根据定义，最后一个状态值只是以 nums[len - 1] 结尾的「上升子序列」的长度；
    • 状态数组 dp 的最大值才是最后要输出的值。
  5. 考虑状态压缩
    • 遍历到一个新数的时候，之前所有的状态值都需要保留，因此无法压缩。

2) 同时用到贪心算法和二分查找

这道题还要求优化到O(nlogn)，这时候需要用到二分查找。

  • 依然是着眼于一个上升子序列的结尾的元素；
  • 如果已经得到的上升子序列的结尾的数越小，遍历的时候后面接上一个数，就会有更大的可能性构成一个更长的上升子序列(贪心法)；
  • 既然结尾越小越好，可以记录在长度固定的情况下，结尾最小的那个元素的数值，这样定义也是为了方便得到「状态转移方程」。

为了与上面解法的状态区分，这里将状态数组命名为 tail 。

  1. 定义新状态（特别重要）
    • ** tail[i] 表示长度为 i + 1 的所有上升子序列的结尾的最小值。**
    • tail[0] 表示长度为 1的所有上升子序列中，结尾最小的那个元素的数值，以题目中的示例为例 [10, 9, 2, 5, 3, 7, 101, 18] 中，容易发现长度为 2 的所有上升子序列中，结尾最小的是子序列 [2, 3] ，因此 tail[1] = 3
    • 下标索引和长度有一个 1 的偏差；

  2. 思考状态转移方程

    • 从直觉上看，数组 tail 也是一个严格上升数组

    证明：反证法(略)，算法步骤：

    1. 设置一个数组 tail ，初始时为空；
    2. 在遍历数组 nums 的过程中，每来一个新数 num，如果这个数严格大于(不包括等于)有序数组 tail 的最后一个元素，就把 num 放在有序数组 tail 的后面，否则进入第 3 点；
    3. 在有序数组 tail 中查找第 1 个等于大于 num 的那个数，试图让它变小；
    • 如果有序数组 tail 中存在等于 num 的元素，什么都不做，因为以 num 结尾的最短的「上升子序列」已经存在；
    • 如果有序数组 tail 中存在大于 num 的元素，找到第 1 个，让它变小，这样我们就找到了一个结尾更小的相同长度的上升子序列。

    说明：再看一下数组 tail[i] 的定义：长度为 i + 1 的所有最长上升子序列的结尾的最小值。因此，在遍历的过程中，我们试图让一个大的值变小是合理的。这一步可以认为是「贪心算法」，总是做出在当前看来最好的选择，当前「最好的选择」是：当前只让让第 1 个严格大于 nums[i] 的数变小，变成 nums[i]，这一步操作是“无后效性”的。由于是在有序数组中的操作，因此可以使用「二分查找算法」。

    1. 遍历新的数 num ，先尝试上述第 2 点，第 2 点行不通则执行第 3 点，直到遍历完整个数组 nums，最终有序数组 tail 的长度，就是所求的“最长上升子序列”的长度。
  3. 初始化 - dp[0] = nums[0] ，在只有 1 个元素的情况下，它当然是长度为 1 并且结尾最小的元素。
  4. 输出 - 数组 tail 的长度，上文其实也已经说了，还是依据定义，tail[i] 表示长度固定为 i + 1 的所有「上升子序列」的结尾元素中最小的那个，长度最多就是数组 tail 的长度。
  5. 考虑状态压缩 - 同样无法压缩

代码

DP 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
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        if (len == 1) {
            return 1;
        }
        //regionLongest[k]表示到第k+1个元素时的最长升序长度；
        //regionLongest[0]表示初始状态（0个元素的时候，依然为1）, 
        //regionLongest[1]表示第0个元素的最长长度，
        //regionLongest[len]表示最后一个元素的最长长度
        int[] regionLongest = new int[len];
        Arrays.fill(regionLongest, 1);//每个位置初始值为1，起码包含自己为1

        for (int i = 1; i <= len - 1; i++) {//从第二个元素开始，让其之前有元素
            for (int j = 0; j < i; j++) {//i之前的状态
                if (nums[j] < nums[i]) {
                    //DP中每个位置存储的值由上一个状态+1组成，因为nums[j] < nums[j]这个条件成立才可能来判断是否要+1（升序多一个），要不然regionLongest[i]就保持不变
                    regionLongest[i] = Math.max(regionLongest[i], regionLongest[j] + 1);
                }
            }
        }

        //找到数组中所有位置的最大升序的数字
        // int globalLongest = 0;
        // for (int longest : regionLongest) {
        //     globalLongest = Math.max(globalLongest, longest);
        // }
        // return globalLongest;
        return Arrays.stream(regionLongest).max().getAsInt();
    }
}

二分查找 O(nlogn)

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
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return len;
        }

        // tail 数组的定义：长度为 i + 1 的上升子序列的末尾最小是几
        int[] tail = new int[len];
        // 遍历第 1 个数，直接放在有序数组 tail 的开头
        tail[0] = nums[0];
        // end 表示有序数组 tail 的最后一个已经赋值元素的索引
        int end = 0;

        for (int i = 1; i < len; i++) {
            // 【逻辑 1】比 tail 数组实际有效的末尾的那个元素还大
            if (nums[i] > tail[end]) {
                // 直接添加在那个元素的后面，所以 end 先加 1
                end++;
                tail[end] = nums[i];
            } else {
                // 使用二分查找法，在有序数组 tail 中
                // 找到第 1 个大于等于 nums[i] 的元素，尝试让那个元素更小
                int left = 0;
                int right = end;
                while (left < right) {
                    // 选左中位数不是偶然，而是有原因的，原因请见 LeetCode 第 35 题题解
                    // int mid = left + (right - left) / 2;
                    int mid = left + ((right - left) >>> 1);
                    if (tail[mid] < nums[i]) {
                        // 中位数肯定不是要找的数，把它写在分支的前面
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                // 走到这里是因为 【逻辑 1】 的反面，因此一定能找到第 1 个大于等于 nums[i] 的元素
                // 因此，无需再单独判断
                tail[left] = nums[i];
            }
            // 调试方法
            // printArray(nums[i], tail);
        }
        // 此时 end 是有序数组 tail 最后一个元素的索引
        // 题目要求返回的是长度，因此 +1 后返回
        end++;
        return end;
    }
}
This site is open source. Improve this page.