【LeetCode】（LISி）最长上升子序列问题及变形应用

迈不过友情╰ 2022-11-10 01:09 32阅读 0赞

## 【LeetCode】（LISி）最长上升子序列问题及变形应用 ##

### 文章目录 ###

*   *  【LeetCode】（LISி）最长上升子序列问题及变形应用
     *   *  马戏团人塔★★
         *  俄罗斯套娃信封问题★★★
         *  堆箱子★★★
         *  堆叠长方体的最大高度★★★
         *  根据身高重建队列★★

[300. 最长递增子序列][300.]

> 关于LIS题目的讲解在[【LeetCode】（动态规划ி）力扣之最][LeetCode]已经很详细了，此处不再赘述

### 马戏团人塔★★ ###

[面试题 17.08. 马戏团人塔][17.08.]

【**题目**】有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。

**提示：**

*  `height.length == weight.length <= 10000`

【**示例**】

输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
    输出：6
    解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)

【**解题思路**】

身高升序排列，若身高相同，按体重降序排列

class Solution {
        
        public int bestSeqAtIndex(int[] height, int[] weight) {
        
            int[][] person = new int[height.length][2];
            for (int i = 0; i < height.length; i++) {
        
                person[i] = new int[]{
        height[i], weight[i]};
            }
            Arrays.sort(person, (o1, o2) -> {
        
                return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
            });
    
            int res = 0;
            int[] dp = new int[person.length];
            for (int[] p : person) {
        
                int i = Arrays.binarySearch(dp, 0, res, p[1]);
                if (i < 0) i = -(i + 1);
                dp[i] = p[1];
                if (i == res) res++;
            }
    
            return res;
        }
    }

--------------------

### 俄罗斯套娃信封问题★★★ ###

[354. 俄罗斯套娃信封问题][354.]

【**题目**】给你一个二维整数数组 `envelopes` ，其中 `envelopes[i] = [wi, hi]` ，表示第 `i` 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

**提示：**

*  `1 <= envelopes.length <= 5000`
 *  `envelopes[i].length == 2`
 *  `1 <= wi, hi <= 104`

【**示例**】

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

【**解题思路**】

将信封按宽度升序排列，若宽度相同则按高度降序排列

class Solution {
        
        public int maxEnvelopes(int[][] envelopes) {
        
            Arrays.sort(envelopes, (a, b) -> {
        
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            });
            int[] dp = new int[envelopes.length];
            int res = 0;
            for (int[] envelope : envelopes) {
        
                int i = Arrays.binarySearch(dp, 0, res, envelope[1]);
                if (i < 0) {
        
                    i = - (i + 1);
                }
                dp[i] = envelope[1];
                if (i == res) {
        
                    res++;
                }
            }
            return res;
        }
    }

--------------------

### 堆箱子★★★ ###

[面试题 08.13. 堆箱子][08.13.]

【**题目**】堆箱子。给你一堆n个箱子，箱子`宽 wi`、`深 di`、`高 hi`。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组`[wi, di, hi]`表示每个箱子。

**提示:**

1.  箱子的数目不大于3000个。

【**示例**】

输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
     输出：6
     -----------------------------------------------------------------
     输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
     输出：10

【**解题思路**】

按其宽深高依次升序排列

class Solution {
        
        public int pileBox(int[][] box) {
        
            Arrays.sort(box, (a, b) -> {
        
                return a[0] == b[0] ? (a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]) : a[0] - b[0];
            });
            int[] dp = new int[box.length];
            int res = 0;
            for (int i = 0; i < box.length; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    if (box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2]) {
        
                        dp[i] = Math.max(dp[i], dp[j]);
                    }
                }
                dp[i] += box[i][2];
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }

--------------------

### 堆叠长方体的最大高度★★★ ###

[1691. 堆叠长方体的最大高度][1691.]

【**题目**】给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 `cuboids[i] = [width_i, length_i, height_i]`（下标从 `0` 开始）。请你从 `cuboids` 选出一个 子集 ，并将它们堆叠起来。

如果 `width_i <= width_j` 且 `length_i <= length_j` 且 `height_i <= height_j` ，你就可以将长方体 `i` 堆叠在长方体 `j` 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。

返回 堆叠长方体 `cuboids` 可以得到的 最大高度 。

**提示：**

*  `n == cuboids.length`
 *  `1 <= n <= 100`
 *  `1 <= widthi, lengthi, heighti <= 100`

【**示例**】

![20210315235800379.jpg_pic_center][]

输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]]
    输出：190
    解释：
    第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
    第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
    第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
    总高度是 95 + 50 + 45 = 190 。

【**解题思路**】

先将每个长方体三元组内部按升序排列，

然后将长方体按长宽高依次升序排列

class Solution {
        
        public int maxHeight(int[][] cuboids) {
        
            for (int[] cuboid : cuboids) {
        
                Arrays.sort(cuboid);
            }
            Arrays.sort(cuboids, (a, b) -> {
        
                return a[0] == b[0] ? (a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]) : a[0] - b[0];
            });
    
            int[] dp = new int[cuboids.length];
            int res = 0;
            for (int i = 0; i < cuboids.length; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
        
                        dp[i] = Math.max(dp[i], dp[j]);
                    } 
                }
                dp[i] += cuboids[i][2];
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }

--------------------

附加题型（同是自定义排序，但这道题思路不易想到）

### 根据身高重建队列★★ ###

[406. 根据身高重建队列][406.]

【**题目**】假设有打乱顺序的一群人站成一个队列，数组 `people` 表示队列中一些人的属性（不一定按顺序）。每个 `people[i] = [hi, ki]` 表示第 `i` 个人的身高为 `hi` ，前面 正好 有 `ki` 个身高大于或等于 `hi` 的人。

请你重新构造并返回输入数组 `people` 所表示的队列。返回的队列应该格式化为数组 `queue` ，其中 `queue[j] = [hj, kj]` 是队列中第 `j` 个人的属性（`queue[0]` 是排在队列前面的人）。

**提示**：

*  `1 <= people.length <= 2000`
 *  `0 <= hi <= 106`
 *  `0 <= ki < people.length`
 *  题目数据确保队列可以被重建

【**示例**】

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
    解释：
    编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
    编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
    编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
    编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
    编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
    编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
    因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

【**解题思路**】

按身高降序排列，若身高相同则按k值升序排列。

之后顺序遍历将元插入结果集中即可

class Solution {
        
        public int[][] reconstructQueue(int[][] people) {
        
            Arrays.sort(people, (o1, o2) -> {
        
                return o1[0] != o2[0] ? (o2[0] - o1[0]) : (o1[1] - o2[1]);
            });
            List<int[]> list = new LinkedList<>();
            for (int i = 0; i < people.length; i++) {
        
                list.add(people[i][1], people[i]);
            }
            return list.toArray(new int[list.size()][]);
        }
    }

[300.]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[LeetCode]: https://blog.csdn.net/weixin_44368437/article/details/113200020
[17.08.]: https://leetcode-cn.com/problems/circus-tower-lcci/
[354.]: https://leetcode-cn.com/problems/russian-doll-envelopes/
[08.13.]: https://leetcode-cn.com/problems/pile-box-lcci/
[1691.]: https://leetcode-cn.com/problems/maximum-height-by-stacking-cuboids/
[20210315235800379.jpg_pic_center]: /images/20221023/41806ebec7834530bf2282e876b77264.png
[406.]: https://leetcode-cn.com/problems/queue-reconstruction-by-height/