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

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
        int n = arr.length;
        if (n < 1) {
            return new int[0];
        }

        // res中存储最长递增子序列，但不一定字典序最小
        int[] res = new int[n];
        // maxLen[i]表示以arr[i]结尾的最长递增子序列的长度
        int[] maxLen = new int[n];
        res[0] = arr[0];
        maxLen[0] = 1;
        int idx_res = 1;
        int idx_len = 1;
        // 第一步：利用贪心+二分求最长递增子序列长度
        for (int i = 1; i < n; i++) {
            if (arr[i] > res[idx_res-1]) {
                res[idx_res++] = arr[i];
                maxLen[idx_len++] = idx_res; 
            } else {
                // 二分
                // 返回有序数组[0..idx_res)中第一个大于等于arr[i]的元素下标
                int pos = binarySearch(res, 0, idx_res - 1, arr[i]);
                res[pos] = arr[i];
                maxLen[idx_len++] = pos + 1;
            }
        }
        // 第二步：填充最长递增子序列
        // 假设 maxLen = {1,2,3,1,3}
        // 那么应该返回以arr[4] 或 arr[2] 为结尾的子序列
        // 要满足字典序所以应返回以 arr[4] 结尾的子序列
        for (int i = n - 1, j = idx_res; j > 0; i--) {
            if (maxLen[i] == j) {
                res[--j] = arr[i];
            }
        }
        int[] ans = new int[idx_res];
        for (int i = 0; i < idx_res; i++) {
            ans[i] = res[i];
        }
        return ans;
    }

    public int binarySearch(int[] arr, int left, int right, int num) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}