题解 | 最长上升子序列(三)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        int n = arr.length;
        // maxLen[i] 记录以 arr[i] 结尾的最长递增子序列的长度
        int[] maxLen = new int[n];
        // tails 记录每个长度的递增子序列结尾的最小值
        int[] tails = new int[n];
        int len = 0; // 当前最长递增子序列的长度

        // 1. 遍历原数组，利用二分查找填充 tails 和 maxLen
        for (int i = 0; i < n; i++) {
            int left = 0, right = len - 1;
            // 二分查找第一个大于等于 arr[i] 的元素位置
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < arr[i]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            // 将 arr[i] 放入 tails 数组
            tails[left] = arr[i];
            // 如果是在末尾追加，说明最大长度增加了
            if (left == len) {
                len++;
            }
            // 记录当前元素对应的 LIS 长度（索引从 0 开始，所以长度是 left + 1）
            maxLen[i] = left + 1;
        }

        // 2. 倒序遍历，还原字典序最小的序列
        int[] res = new int[len];
        int currLen = len;
        // 设一个初始安全最大值，题目范围最大 10^9，Integer.MAX_VALUE 足够大
        int lastVal = Integer.MAX_VALUE;

        for (int i = n - 1; i >= 0; i--) {
            // 如果长度匹配，并且当前值严格小于后面的值（保证递增）
            if (maxLen[i] == currLen && arr[i] < lastVal) {
                res[currLen - 1] = arr[i];
                lastVal = arr[i];
                currLen--;
            }
        }

        return res;
    }
}