最长递增子序列进阶

最长递增子序列（LeetCode 300）复习

基础 LIS 两种解法：

// O(n²) DP 解法
public int lengthOfLIS(int[] nums) {
    int n = nums.length, ans = 1;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

// O(n log n) 贪心 + 二分
public int lengthOfLIS2(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    for (int num : nums) {
        int lo = 0, hi = tails.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails.get(mid) < num) lo = mid + 1;
            else hi = mid;
        }
        if (lo == tails.size()) tails.add(num);
        else tails.set(lo, num);
    }
    return tails.size();
}

俄罗斯套娃（LeetCode 354）

信封按宽度排序，宽度相同则高度降序，然后对高度求 LIS：

关键：宽度相同时高度降序，防止宽相同的多个信封被套进同一个 LIS

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) ->
        a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]); // 宽升序，宽相同高降序
    // 对高度求 LIS（O(n log n)）
    int[] tails = new int[envelopes.length];
    int size = 0;
    for (int[] e : envelopes) {
        int h = e[1], lo = 0, hi = size;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < h) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = h;
        if (lo == size) size++;
    }
    return size;
}

最长递增子序列的个数（LeetCode 673）

public int findNumberOfLIS(int[] nums) {
    int n = nums.length, maxLen = 0, ans = 0;
    int[] dp = new int[n]; // dp[i] = 以 nums[i] 结尾的 LIS 长度
    int[] cnt = new int[n]; // cnt[i] = 以 nums[i] 结尾的 LIS 个数
    Arrays.fill(dp, 1);
    Arrays.fill(cnt, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; cnt[i] = cnt[j]; }
                else if (dp[j] + 1 == dp[i]) cnt[i] += cnt[j];
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    for (int i = 0; i < n; i++) if (dp[i] == maxLen) ans += cnt[i];
    return ans;
}

总结