[数据结构与算法]最长上升子序列

题目链接

最长上升子序列

题目描述

注意

• 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序
• 尽量节省时间

解答思路

• 遍历整个数组，从左到右动态规划计算以每个元素为尾部元素的最长上升子序列：储存每个元素的最长上升子序列，当访问到某个元素时，从左往右遍历其前方的所有元素，找到比当前元素小的尾部值中最长上升子序列的最大值，在最大值的基础上加1就是以当前元素为尾部值的最长上升子序列
• 在动态规划的基础上，采用二分查找寻找在当前元素之前的元素的最长上升子序列的最大值。方法是用一个tails数组存储上升序列长度为i的最小尾部值，其实际长度为当前的最长上升子序列，则该tails数组是单调递增的。遍历到每个元素时，判断如果此时tails数组中的最长上升序列的尾部元素的值都小于此时的元素值，则更新最长上升序列，并更新tails数组中的实际长度以及该长度处的最小尾部值为当前元素值；否则在tails实际数组范围中查找出第一个比当前元素值大的位置，并更新其值为当前元素值

代码

// 动态规划 + 二分查找
class Solution {
    public int lengthOfLIS(int[] nums) {
        // tails数组用来存储长度为i + 1的子序列尾部元素的最小值
        // 该数组一定是递增的
        int[] tails = new int[nums.length];
        tails[0] = nums[0];
        
        int res = 1;

        for(int num : nums) {
            // 左边界
            int i = 0;
            // 由边界为此时tails数组的填充长度，也是此时的最长子序列
            int j = res;

            // 如果此时tails数组中所有的值都小于当前的数值，则更新最长子序列
            if(tails[res - 1] < num) {
                tails[res] = num;
                res++;
                continue;
            }

            // 其余情况二分查找第一个比当前数值大的tails值
            while(i < j) {              
                int m = (i + j) / 2;
                if(tails[m] < num) {
                    // 向右查找
                    i = m + 1;
                }
                else {
                    // 向左查找
                    j = m;
                }
            }
            // 更新第一个比当前数字大的tails值为当前的数值
            tails[i] = num;
        }
        return res;
    }
}

关键点

• 通过tails数组存储存储上升序列长度为i的最小尾部元素的值
• tails数组是单调递增的
• 当tails数组实际范围中存在比当前元素值大的尾部值，则需要找到满足该条件的第一个值在tails数组中的位置，并更新该位置的值为当前元素值，以保证该位置处的tails值是最小尾部值