耐心排序之最长递增子序列(LIS)

港控/mmm° 2024-03-24 09:53 76阅读 0赞

**目录**

一.问题引入

1.最长递增子序列(LIS)

2.问题分析

3.代码实现

4.问题思考

二.耐心排序

1.基本介绍

2.操作步骤

3.代码实现

三.俄罗斯套娃信封问题

1.题目描述

2.问题分析

3.代码实现

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

## 一.问题引入 ##

### 1.最长递增子序列(LIS) ###

先来看题目 力扣:[力扣][Link 1]

> 给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。
> 
> **子序列** 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。

相信我们在刷**动态规划**题目的时候都遇到过这个问题,这个问题就是寻找最长递增子序列

**注:子序列不一定要连续.**

### **2.问题分析** ###

这一题首先要理解子序列问题,子序列不一定是连续一段的数组(子数组),只需要它的序列是递增的即可(例如index=0,2,3)

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

**1.确定dp数组（dp table）以及下标的含义**

本题的dp数组定义不是根据题目直接来进行定义,需要根据题意进行变通定义

dp\[i\]数组的含义:以nums\[i\]为结尾的最长递增子序列长度为dp\[i\]

注意:这里一定要以nums\[i\]为结尾,不可去除这个元素

**2.确定递推公式**

位置i的元素最长的递增子序列等于位置从0到j-1位置上最长递增子序列+1的最大值

递推公式:if (nums\[i\] > nums\[j\]) dp\[i\] = max(dp\[i\], dp\[j\] + 1);

注意:这里dp\[i\] = max(dp\[i\], dp\[j\] + 1)是为了取dp\[i\]的最大值,并不是dp\[i\]和dp\[j\] + 1比较

注意:这里它的最大值并不一定出现在dp\[nums.length-1\]的位置,如何最后一个数字比前边的都小,而dp数组的定义必须以nums\[i\]为结尾,所有此时dp\[i\]的值可能为1,因为应该取dp数组元素的最大值

**3.dp数组如何初始化**

由题意可知,无论前边的nums\[j\]是否比nums\[i\]大,总有一个元素满足递增序列,就是它本身自己,所有每一个dp\[i\]都应该初始化为1

**4.确定遍历顺序**

因为最长递增子序列是从前到后递增,所以我们也应该从左到右进行遍历

**5.举例推导dp数组**

对nums = \[10,9,2,5,3,7,101,18\]进行推导  
i 0 1 2 3 4 5 6 7  
dp\[i\] 1 1 1 2 2 3 4 4

它的最长的递增序列是\{2,3,7,101\}或者\{2,3,7,18\}

### 3.代码实现 ###

public int lengthOfLIS(int[] nums) {
            int[] dp = new int[nums.length];
            int max = 1;
            Arrays.fill(dp, 1);
            for (int i = 1; i < nums.length; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (nums[i] > nums[j])
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                max = Math.max(max, dp[i]);
            }
     
            return max;
     
        }

### 4.问题思考 ###

这一题我们可以利用动态规划的思想解决出来,并且时间复杂度为O(n),; 但是有一种更快速的方法,时间复杂度可以更低,这种方法利用了二分查找

## 二.耐心排序 ##

### 1.基本介绍 ###

**耐心排序**（Patience Sort）是将数组的元素**分类成很多堆再串接回数组的一种排序算法**,这一种排序算法受到一种叫做patience game的纸牌游戏的启发,主要用于解决**最长递增子序列的问题**

### **2.操作步骤** ###

*  创建一个**堆数组**
 *  **比较目前**指向的**元素**和**每个堆**的**第一个元素**，计算出比目前元素小的堆
 *  若目前元素**比所有堆的第一个元素大**，**创建新的堆**并加入到堆数组中，否则将目前元素加入到最先创建的堆(也就是最左边的堆);
 *  所有元素放入堆之后,每个堆的有一个元素为最长递增子序列中的元素(但不知道具体是第几个),堆的个数就是最长递增子序列的长度

**举例演示: 将\{** 3, 5, 7, 1, 4**\}进行耐心排序**

**第一步:将3放入堆中,因为没有堆,新建一个堆放入**

*  **堆1:内容:3**

**第二步:将5放入堆中,因为5比一号堆的第一个元素大,新建一个堆放入**

*  **堆1:内容:3**
 *  **堆2:内容:5**

**第三步:将7放入堆中,因为7比一号堆和二号堆的第一个元素都大,新建一个堆放入**

*  **堆1:内容:3**
 *  **堆2:内容:5**
 *  **堆3:内容:7**

**第四步:将1放入堆中,因为1比堆1的第一个元素小,将1放入堆1中**

*  **堆1:内容:3,1**
 *  **堆2:内容:5**
 *  **堆3:内容:7**

**第四步:将4放入堆中,因为4比堆一的元素大,但是4比堆二的元素小,所以将4放入堆2中**

*  **堆1:内容:3,1**
 *  **堆2:内容:5,4**
 *  **堆3:内容:7**

**由此我们可以知道最长递增子序列的长度为堆的个数:3**

**现在我尝试用代码写出来解决这个问题**

### **3.代码实现** ###

**这个代码的实现需要二分查找的相关知识,不是很懂的可以参考这篇博客:**[二分查找变式讲解\_允歆辰丶的博客-CSDN博客][-CSDN]

**这个代码的实现还是有许多注意点的**

**注意点一:我们初始化一个top数组,用来记录各个堆的堆顶元素,长度为nums.length,因为最长的递增子序列最多也就是nums.length个元素(也就是原本数组严格单调递增),最多需要开辟nums.length个堆即可**

**注意点二:我们只需要记录堆顶的元素即可,因为只需要堆顶元素和当前元素对比,判断是否符合插入的条件即可;**

**注意点三:pile记录的是堆的个数,也就是top数组的实际长度,因此二分查找的时候注意要pile-1才是最右端堆的索引**

**注意点四:当前元素等于某个堆顶元素时,我们不需要开辟新的堆,直接将该元素变为此堆的堆顶即可,因为严格递增子序列,后边的元素一定是大于前边的元素的,例如\{7,7,7\}数组,这个时候只需要开辟一个堆即可.**

**注意点五:当二分查找返回的是pile的时候,这个时候表示未找到小于当前元素的堆,这时候需要开辟一个新的堆,我们直接让pile++,相当于多了一个堆,将当前元素放入到新开辟的堆,也是:top\[index\] = poker;**

public int lengthOfLIS(int[] nums) {
            //默认有num.length个堆,只记录堆顶(最多也只可能这么多个堆)
            int[] top = new int[nums.length];
            int pile = 0;//现在堆的个数
            for (int i = 0; i < nums.length; ++i) {
                int poker = nums[i];
                //堆的长度为pile,所以最右端堆的索引为pile-1;
                int index = binarySearch(top, pile - 1, poker);
                //没有找到比poker小的堆,新开辟一个堆
                if (index == pile) {
                    pile++;
                }
                top[index] = poker;
    
            }
            return pile;
    
        }
    
        //二分查找目的:查找到第一个比poker小的堆顶的位置
        //开辟堆的条件,没有找到(当前元素)严格小于堆顶元素的堆
        //如果当前元素等于堆顶元素,不需要开辟堆;如果开辟了,就不符合严格递增的条件了
        public int binarySearch(int[] top, int right, int target) {
            int left = 0;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (top[mid] >= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }

## 三.俄罗斯套娃信封问题 ##

之前问题解决了之后,来解决一下这个问题,也是一道耐心排序的问题

### 1.题目描述 ###

> 给你一个二维整数数组 `envelopes` ，其中 `envelopes[i] = [wi, hi]` ，表示第 `i` 个信封的宽度和高度。
> 
> 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
> 
> 请计算 **最多能有多少个** 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
> 
> **注意**：不允许旋转信封。

力扣:[力扣][Link 2]

### 2.问题分析 ###

这一题还是有一定的难度的,因为前一题是一维的数组,这一题转化为了二维的,而且题目还没有明说是最长递增子序列,那我们该如何将这一题转化为一维的求最长递增子序列的问题呢?题目的意思是一个信封的宽度和高度都比另一个大的时候才可以嵌套下去,那么我们可以对宽度(高度)进行排序,然后只需要找到对于高度(宽度)的最长递增子序列即可.但是有一个**注意点,当宽度相同的时候,即使一个高度比另一个高,也是不可嵌套的,比如\{\[6,4\],\[6,7\]\},但是排序之后可能出现此种顺序,这个时候根据高度的最长递增子序列就是2,不符合题意,因此我们进行如下处理:当宽度相同的时候,高度按递减排序,这样就不存在满足递增子序列的情况了,这样排序后的数组如下\{\[6,7\],\[6,4\]\};**

**上一题我们使用了数组来实现,这一题我们采用ArrayList来实现耐心排序,其实这样更加的方便**

### 3.代码实现 ###

public int maxEnvelopes(int[][] envelopes) {
            //对宽度进行递增排序,宽度相同,高度按递减排序
            Arrays.sort(envelopes, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if (o1[0] == o2[0])
                        return o2[1] - o1[1];
                    return o1[0] - o2[0];
                }
            });
            //开辟的堆
            List<Integer> pile = new ArrayList<Integer>();
            pile.add(envelopes[0][1]);//第一个可以开辟一个堆加入
            for (int i = 1; i < envelopes.length; ++i) {
                int poker = envelopes[i][1];
                int index = binarySearch(pile, poker);
                //未找到,开辟一个新堆
                if (index == pile.size()) {
                    pile.add(poker);
                } else {
                    //修改堆顶的元素
                    pile.set(index, poker);
                }
            }
            return pile.size();
        }
    
        //二分查找目的:查找到第一个比poker小的堆顶的位置
        //开辟堆的条件,没有找到(当前元素)严格小于堆顶元素的堆
        //如果当前元素等于堆顶元素,不需要开辟堆;如果开辟了,就不符合严格递增的条件了
        public int binarySearch(List<Integer> pile, int target) {
            int left = 0, right = pile.size() - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (pile.get(mid) >= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }

动态规划的解法在这里写出,但是题目提交的时候会出现超时

//转化为最长递增子序列的问题
        public int maxEnvelopes(int[][] envelopes) {
            //对宽度进行递增排序,宽度相同,高度按递减排序
            Arrays.sort(envelopes, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if (o1[0] == o2[0])
                        return o2[1] - o1[1];
                    return o1[0] - o2[0];
                }
            });
            //动态规划
            int[] dp = new int[envelopes.length];
            Arrays.fill(dp, 1);
            int max = 0;
            for (int i = 1; i < dp.length; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (envelopes[i][1] > envelopes[j][1])
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                max = Math.max(max, dp[i]);
            }
            return max;
    
        }

[Link 1]: https://leetcode.cn/problems/longest-increasing-subsequence/
[-CSDN]: https://blog.csdn.net/qq_64580912/article/details/128442143
[Link 2]: https://leetcode.cn/problems/russian-doll-envelopes/