mzoe666888

V1

2022/04/10阅读:23主题:兰青

内卷大厂系列《最长递增子序列问题五连击》

大厂高频算法面试题:《最长递增子序列系列》,您将学到最长递增子序列的经典模型,从经典模型出发引出一系列问题,其核心本质还是最长递增子序列模型,本文将从两种方法讲解,时间复杂度为O(N²)的解,时间复杂度为O(N*logN)的最优解。

欢迎关注《内卷学苑》

一、最长递增子序列 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<Envelope{
    @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;
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1