2021/1/28 最长递增子序列

题目描述

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）

示例1

输入

[2,1,5,3,6,4,8,9,7]

返回值

[1,3,4,8,9]

示例2

输入

[1,2,8,6,4]

返回值

[1,2,4]

说明

其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）

解题思路

下面的“标号”讲的过于抽象，我推荐《最长递增子序列 - murphy_gb - 博客园》 这篇文章，里面的动图很形象。

1. 我们将大问题拆分为小问题，把数组缩短，再慢慢加长直到完整。如示例 1 中 原数组 arr = [2, 1, 5, 3, 6, 4, 8, 9, 7] 我们把最初的子问题定为 [2, 1]，下一个子问题既往后加长一位 [2, 1, 5]，以此类推。
2. 为了能在遍历完子问题后精确地在原数组 arr 中找出组成最长递增子序列 LCS 的元素，我们可以使用“标号”的方法，在 arr 中组成 LCS 的元素上标上序号，比如示例 1 中 arr = [2, 1, 5, 3, 6, 4, 8, 9, 7]， LCS = [1, 3, 4, 8, 9]，LCS[0] = arr[1]，LCS[1] = arr[3]，LCS[2] = arr[5]。所以如何标号就是这个问题的关键。
   
3. 如何标号呢？我们需要新增一个数组 temp，每当子问题增加一个元素 e 时，e 就与 temp 最后一个元素就进行比较，如果 e 比 temp 的最后一个元素大，则直接在 temp 最后面添加 e；反之，则在 temp 中从左往右寻找第一个比 e 大的数，并用 e 替换之。然后 e 在 temp 中的索引就是我们要找的标号，我们将标号存起来，继续下一个子问题。
   
4. 在 nums 中标完号后，为了满足题目要求的字典序最小，我们需要从后往前遍历，标号从大到小，倒着填入 LCS 中，最后我们获得结果 LCS。
   

Java代码实现

public class Solution {

    public int[] LIS (int[] arr) {
        int[] nums = new int[arr.length];
        int[] temp = new int[arr.length];
        nums[0] = 1;
        int tempIndex = 0;
        temp[tempIndex] = arr[0];
        for (int i = 1; i < arr.length; ++i) {
            int left = 0, right = tempIndex;
            if (arr[i] > temp[tempIndex]) {
                ++tempIndex;
                nums[i] = tempIndex + 1;
                temp[tempIndex] = arr[i];
            } else {
                while (left <= right) {        // 注意这里 left <= right 而不是 left < right，我们要替换的是第一个比 arr[i] 大的元素
                    int mid = (right + left) / 2;
                    if (temp[mid] > arr[i]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                temp[left] = arr[i];
                nums[i] = left + 1;
            }
        }

        int[] res = new int[tempIndex + 1];
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] == tempIndex + 1) {
                res[tempIndex] = arr[i];
                --tempIndex;
            }
        }
        return res;
    }

}