当前位置：网站首页>【Leetcode】最长递增子序列问题及应用

【Leetcode】最长递增子序列问题及应用

2022-06-23 03:54:00 【小朱小朱绝不服输】

文章目录

- - 最长递增子序列问题及应用

最长递增子序列问题及应用

300. 最长递增子序列

请参考【Leetcode】计算最长系列（动态规划）中对 300. 最长递增子序列的讲解。解题方法主要有两种：动态规划、贪心+二分查找。

面试题 17.08. 马戏团人塔

1.题目描述

leetcode链接：面试题 17.08. 马戏团人塔
在这里插入图片描述

2.思路分析

题目要求在2个维度上(即身高 + 体重)同时保持严格递增。

那么我们可以先将其中一个维度排好序，以保证在一个维度上保持递增（此时并非严格递增）；之后就可以专注于处理另一个维度。

先对身高体重排序，身高升序排列，身高相同，体重降序排列，这里可以使用二维数组的lambda表达式写法。可以参考：Java数组、ArrayList、HashMap排序总结。

之后就是计算最长递增子序列。身高已经按升序了，只需要判断体重。处理体重的问题就是处理最长递增子序列的问题。

参考最长递增子序列的解法。

3.参考代码

方法一：动态规划（超时）

class Solution {
    
    public int bestSeqAtIndex(int[] height, int[] weight) {
    
        int n = height.length;
        int[][] person = new int[n][2];
        for (int i = 0; i < n; i++) {
    
            person[i] = new int[]{
    height[i], weight[i]};
        }
        // 身高相同，体重降序
        Arrays.sort(person, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int i = 0; i < n; i++) {
    
            for (int j = 0; j < i; j++) {
    
                if (person[i][1] > person[j][1]) {
    
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(dp[i], res); 
        }
        return res;
    }
}

方法二：贪心 + 二分查找

class Solution {
    
    public int bestSeqAtIndex(int[] height, int[] weight) {
    
        int n = height.length;
        int[][] person = new int[n][2];
        for (int i = 0; i < n; i++) {
    
            person[i] = new int[]{
    height[i], weight[i]};
        }
        // 身高相同，体重降序
        Arrays.sort(person, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int[] per : person) {
    
            int left = 0, right = res;
            while (left < right) {
    
                int mid = (right - left) / 2 + left;
                if (dp[mid] < per[1]) {
      // 要找的是dp数组中第一个小于当前h的位置
                    left = mid + 1;
                } else {
    
                    right = mid;
                }
            }
            dp[left] = per[1];
            if (res == left) res++;
        }
        return res;
    }
}

二分查找可以直接调API：

通过二分法在已经排好序的数组中查找指定的元素，并返回该元素的下标。

如果数组中存在该元素，则会返回该元素在数组中的下标
如果数组中不存在该元素，则会返回 -(插入点 + 1)

int res1 = Arrays.binarySearch(int[] arr, int key);  // 默认搜索整个数组
int res2 = Arrays.binarySearch(int[] arr, int fromIndex, int toIndex, int key);  // 搜索数组指定索引内

class Solution {
    
    public int bestSeqAtIndex(int[] height, int[] weight) {
    
        int n = height.length;
        int[][] person = new int[n][2];
        for (int i = 0; i < n; i++) {
    
            person[i] = new int[]{
    height[i], weight[i]};
        }
        // 身高相同，体重降序
        Arrays.sort(person, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int[] per : person) {
    
            int i = Arrays.binarySearch(dp, 0, res, per[1]);
            if (i < 0) i = -(i + 1); // 如果没找到
            dp[i] = per[1];
            if (i == res) res++;
        }
        return res;
    }
}

354. 俄罗斯套娃信封问题

1.题目描述

leetcode链接：354. 俄罗斯套娃信封问题
在这里插入图片描述

2.思路分析

与上一题相同，只是身高体重的区间换成了信封的长宽，方法完全一样。

直接动态规划会超时，所以可以还是使用二分查找来优化。

3.参考代码

class Solution {
    
    public int maxEnvelopes(int[][] envelopes) {
    
        int n = envelopes.length;
        Arrays.sort(envelopes, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 初始化为1，表示当前信封
        int max = 0;
        // 二分查找
        for (int[] env : envelopes) {
    
            int left = 0, right = max;
            while (left < right) {
    
                int mid = (right - left) / 2 + left;
                if (dp[mid] < env[1]) {
      // 要找的是dp数组中第一个小于当前h的位置
                    left = mid + 1;
                } else {
    
                    right = mid;
                }
            }
            dp[left] = env[1];
            if (left == max) {
    
                max++;
            }
        }
        return max;
    }
}