最长递增子序列「变题」

300. 最长递增子序列

开头先来一个小插曲，关于「最长递增子序列」问题的总结可见 动态规划设计：最长递增子序列

// 时间复杂度 : O(n^2)
// 空间复杂度 : O(n)
public int lengthOfLIS(int[] nums) {
    int n = nums.length, ans = 0;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

变题一：时间优化成 O(nlogn)

// 时间复杂度 : O(nlogn)
// 空间复杂度 : O(n)
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] top = new int[n];
    int piles = 0;
    for (int i = 0; i < n; i++) {
        int poker = nums[i];
        int l = 0, r = piles;
        while (l < r) {
            int m = l + r >> 1;
            if (top[m] >= poker) r = m;
            else l = m + 1;
        }
        if (l == piles) top[piles++] = poker;
        else top[l] = poker;
    }
    return piles;
}

变题二：输出最长上升子序列，字典序最小

题目详情可见 最长上升子序列(三)

public int[] LIS (int[] nums) {
    int n = nums.length;
    // p 记录每个数在哪个堆中
    int[] top = new int[n], p = new int[n];
    int piles = 0;
    for (int i = 0; i < n; i++) {
        int poker = nums[i];
        int l = 0, r = piles;
        while (l < r) {
            int m = l + r >> 1;
            if (top[m] >= poker) r = m;
            else l = m + 1;
        }
        if (l == piles) {
            top[piles++] = poker;
            p[i] = piles;
        } else {
            top[l] = poker;
            p[i] = l + 1;
        }
    }

    int[] ans = new int[piles];
    for (int i = n - 1; i >= 0; i--) {
        if (p[i] == piles) ans[--piles] = nums[i];
    }
    return ans;
}

变题三：最长非上升子序列，输出且字典序最小

public int[] LIS (int[] nums) {
    int n = nums.length;
    // p 记录每个数在哪个堆中
    int[] top = new int[n], p = new int[n];
    int piles = 0;
    for (int i = 0; i < n; i++) {
        int poker = nums[i];
        int l = 0, r = piles;
        while (l < r) {
            int m = l + r >> 1;
            // 反过来
            if (top[m] < poker) r = m;
            else l = m + 1;
        }
        if (l == piles) {
            top[piles++] = poker;
            p[i] = piles;
        } else {
            top[l] = poker;
            p[i] = l + 1;
        }
    }
    int cp = 0;
    int[] ans = new int[piles];
    // 正向遍历
    for (int i = 0; i < n; i++) {
        if (p[i] == cp + 1) ans[cp++] = nums[i];
    }
    return ans;
}