题解 | #最长递增子序列#

运行时间：330ms
超过72.73% 用Java提交的代码
占用内存：26716KB
超过99.44%用Java提交的代码

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {

//         [2,1,5,3,6,4,8,9,7]   
//         1b---------------------------
//         15a---------------------------
//         13b---------------------------
//         136a---------------------------
//         134b---------------------------
//         1348a---------------------------
//         13489a---------------------------
//         13479b---------------------------
//         lens: [1, 1, 2, 2, 3, 3, 4, 5, 4]
//         [1, 3, 4, 8, 9]

    /**
     * resultList : 存放临时递增子序列
     *      2 -> 1 -> 15 -> 13  将list中的替换为最小的(比如5->3)，并不会影响到子序列的长度
     *      13489a --> 13479b----------以7结尾的长度就是j+1 = 4
     */
        ArrayList<Integer> resultList = new ArrayList<>();
        int[] lens = new int[arr.length];
        lens[0] = 1;
        resultList.add(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            // 直接加入序列，并更新以arr[i]结尾的最长子序列长度
            if (resultList.get(resultList.size()-1) < arr[i]) {
                resultList.add(arr[i]);
                lens[i] = resultList.size();

//                 resultList.forEach(System.out::print);
//                 System.out.println("a---------------------------");
            }else {
                // 找出arr[i] 该在的地方即 比arr[i]小的那个数后面，
                // 以arr[i]结尾的最长子序列长度就是arr[i]的索引+1
                for (int j = resultList.size()-1; j >= 0 ; j--) {
                    if (resultList.get(j) < arr[i]){
                        resultList.set(j+1,arr[i]);
                        lens[i] = j+2;
                        break;
                    }
                    //这里是找不到比arr[i]小的情况，arr[i]最小
                    if (j == 0) {
                        resultList.set(0,arr[i]);
                        lens[i] = 1;
                    }
                }
//                 resultList.forEach(System.out::print);
//                 System.out.println("b---------------------------");
            }
        }
//         System.out.println("lens:" + Arrays.toString(lens));
        int[] res = new int[resultList.size()];
        for (int i = lens.length-1, j = resultList.size(); i >= 0; i--) {
            // 只有当i结尾的最长递增子序列长度等于 j 才可将数组的值付给res
            if (lens[i] == j){
                res[--j] = arr[i]; 
            }
        }
        return res;

    }
}