一、最长递增子序列 I

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

leetcode

1、分析

最长递增子序列经典模型题，子序列不一定连续，子串一定连续！

方法一：动态规划，定义dp[i]含义：必须以i结尾的最长递增子序列是多长，遍历数组，当前来到i位置，往左边找所有小于当前数的最大dp值max(dp[0~i-1])，然后再加个1就是当前最长递增子序列长度，时间复杂度为O(N²)

方法二：引入ends数组，加入求解左边遍历求解最大dp值的过程，ends[i]含义：找到的所有长度为i+1的递增子序列中最小结尾是什么，ends数组必须有序（从小到大），时间复杂度为O(N*logN)

策略：arr中的任何数，去ends数组有效区中找 当前数 的最左侧的位置，如果能找到，则更新ends[i] = cur，然后看这个位置（ends中的i位置）包含自己左侧有几个数就是dp[i]中的值，如果在ends中没有找到 当前数 的最左侧的数，则扩充ends有效区，让ends[i] = arr[i]

2、实现

2.1、方法一

public static int lengthOfLIS(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int[] dp = new int[arr.length];
    dp[0] = 1; // 0位置的最长递增子序列长度为1
    int maxans = 1;
    for (int i = 1; i < arr.length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) { // 0~i-1位置找所有小于当前数的dp值
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxans = Math.max(maxans, dp[i]); // 更新最大值
    }
    return maxans;
}

2.2、方法二

public static int lengthOfLIS(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int[] ends = new int[arr.length];
    ends[0] = arr[0]; // ends[i]的含义找到长度为i+1的递增子序列中最小结尾是什么，0位置就是长度为0+1=1的递增子序列中最小结尾就是数组arr[0]位置的数
    int right = 0; // 有效区 0...right有效，right右边无效
    int L = 0; // 左指针
    int R = 0; // 右指针
    int M = 0; // 中间指针
    int max = 1;
    for (int i = 1; i < arr.length; i++) {
        L = 0;
        R = right;
        while (L <= R) { // 二分查找
            M = (L + R) / 2;
            if (arr[i] > ends[M]) {
                L = M + 1;
            } else {
                R = M - 1;
            }
        }
        // L = right + 1
        right = Math.max(right, L);
        ends[L] = arr[i];
        max = Math.max(max, L + 1);
    }
    return max;
}

二、最长递增子序列 II

给定一个未排序的整数数组 nums ， 以数组形式返回最长递增子序列，如果有多个最长递增子序列，返回一个即可 。

注意 这个数列必须是 严格 递增的。

示例:

输入: [1,3,5,4,7]
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

1、分析

直接用最优解，时间复杂度为O(N*logN)，生成最长递增子序列数组

2、实现

public static int[] lis2(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    int[] dp = getdp2(arr); // 生成最长递增子序列数组dp，每个位置代表当前位置的最长递增子序列长度
    return generateLIS(arr, dp); // 生成最长递增子序列
}

public static int[] getdp2(int[] arr) {
    int[] dp = new int[arr.length];
    int[] ends = new int[arr.length];
    ends[0] = arr[0];
    dp[0] = 1;
    int right = 0; // 有效区  0....right  right往右无效
    int L = 0;
    int R = 0;
    int M = 0;
    for (int i = 1; i < arr.length; i++) {
        L = 0;
        R = right;
        while (L <= R) { // 二分查找的过程
            M = (L + R) / 2;
            if (arr[i] > ends[M]) {
                L = M + 1;
            } else {
                R = M - 1;
            }
        }
        // L -> right+1
        right = Math.max(right, L);
        ends[L] = arr[i];
        dp[i] = L + 1;
    }
    return dp;
}

public static int[] generateLIS(int[] arr, int[] dp) {
    int len = 0; // 最长递增子序列的长度
    int index = 0; // 最长递增子序列的下标
    for (int i = 0; i < dp.length; i++) {
        if (dp[i] > len) {
            len = dp[i];
            index = i;
        }
    }
    int[] lis = new int[len]; // 准备长度为len的递增子序列
    lis[--len] = arr[index];
    for (int i = index; i >= 0; i--) { // 从后往前推
        if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
            lis[--len] = arr[i];
            index = i;
        }
    }
    return lis;
}

三、最长递增子序列 III

每个信封都有长和宽两个维度的数据，A信封如果想套在B信封里面，A信封必须在长和宽上都小于B信封才行。如果给你一批信封，返回最大的嵌套层数。

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

leetcode

1、分析

信封套娃问题（俄罗斯套娃问题）

先按照信封的长度从小到大排序，如果长度相同，在按照信封的宽度（高度）从大到小排序

把信封的宽度（高度）依次提取出来，求最长递增子序列的长度就是能套几层

假如某个信封的宽度为V，因为信封是按照长度从小到大排序的，之前的信封长度必然小于等于当前信封，宽度（高度）又是从大到小排序的，之后的宽度（高度）必然小于等于当前信封，所以这道题的本质就是求按照信封的宽度（高度）最长递增子序列长度是多长，就代表信封能套几层。

2、实现

public static class Envelope {
    public int l; // 信封的长度
    public int h; // 信封的高度

    public Envelope(int weight, int height) {
        l = weight;
        h = height;
    }
}

// 先按照信封的长度从小到大排序，如果长度相等按照信封的高度从大到小排序
public static class EnvelopeComparator implements Comparator {
    @Override
    public int compare(Envelope o1, Envelope o2) {
        return o1.l != o2.l ? o1.l - o2.l : o2.h - o1.h;
    }
}

public static Envelope[] getSortedEnvelopes(int[][] matrix) {
    Envelope[] res = new Envelope[matrix.length];
    for (int i = 0; i < matrix.length; i++) {
        res[i] = new Envelope(matrix[i][0], matrix[i][1]);
    }
    Arrays.sort(res, new EnvelopeComparator());
    return res;
}

public static int maxEnvelopes(int[][] matrix) {
    Envelope[] envelopes = getSortedEnvelopes(matrix);
    int[] ends = new int[matrix.length];
    ends[0] = envelopes[0].h;
    int right = 0; // 有效区
    int L = 0;
    int R = 0;
    int M = 0;
    for (int i = 1; i < envelopes.length; i++) {
        L = 0;
        R = right;
        while (L <= R) {
            M = (L + R) / 2;
            if (envelopes[i].h > ends[M]) {
                L = M + 1;
            } else {
                R = M - 1;
            }
        }
        // L = right + 1
        right = Math.max(right, L);
        ends[L] = envelopes[i].h;
    }
    return right + 1;
}

四、最长递增子序列 IV

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

leetcode

1、分析

矩阵中求最长递增子序列问题，只能上下左右4个方向走动，不能走重复路，对走过的路要标记

时间复杂度O(N*M)，每个位置走一遍，然后上下左右走一遍，即5遍，忽略常数项。

2、实现

public static int longestIncreasingPath(int[][] matrix) {
    int ans = 0;
    int N = matrix.length;
    int M = matrix[0].length;
    int[][] dp = new int[N][M]; // 增加路径标记，防止重复走路
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) { // 每个位置都4个方向走
            ans = Math.max(ans, process(matrix, i, j, dp));
        }
    }
    return ans;
}

private static int process(int[][] matrix, int i, int j, int[][] dp) {
    if (dp[i][j] != 0) { // 说明路走过，直接从dp中拿值
        return dp[i][j];
    }
    int N = matrix.length;
    int M = matrix[0].length;
    // 上
    int up = i > 0 && matrix[i][j] < matrix[i - 1][j] ? process(matrix, i - 1, j, dp) : 0;
    // 下
    int down = i < (N - 1) && matrix[i][j] < matrix[i + 1][j] ? process(matrix, i + 1, j, dp) : 0;
    // 左
    int left = j > 0 && matrix[i][j] < matrix[i][j - 1] ? process(matrix, i, j - 1, dp) : 0;
    // 右
    int right = j < (M - 1) && matrix[i][j] < matrix[i][j + 1] ? process(matrix, i, j + 1, dp) : 0;
    int ans = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    dp[i][j] = ans;
    return ans;
}

五、最长递增子序列 V

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2：

输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

示例 3：

输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

leetcode

1、分析

递增的三元子序列，还是最长递增子序列问题。

2、实现

public static boolean increasingTriplet(int[] arr) {
    if (arr == null || arr.length < 3) {
        return false;
    }
    int[] ends = new int[3];
    ends[0] = arr[0];
    int right = 0; // 有效区
    int l = 0;
    int r = 0;
    int m = 0;
    for (int i = 1; i < arr.length; i++) {
        l = 0;
        r = right;
        while (l <= r) {
            m = (l + r) / 2;
            if (arr[i] > ends[m]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        // l = right + 1
        right = Math.max(right, l);
        if (right > 1) { // 0 1 2
            return true;
        }
        ends[l] = arr[i];
    }
    return false;
}

小伙伴们有兴趣想了解内容和更多相关学习资料的请点赞收藏+评论转发+关注我，后面会有很多干货。我有一些面试题、架构、设计类资料可以说是程序员面试必备！所有资料都整理到网盘了，需要的话欢迎下载！私信我回复【000】即可免费获取

作者：mzoe666888

原文出处：https://mdnice.com/writing/fb95914364e3430d916e83976165b974