LeetCode 354. 俄罗斯套娃信封问题（最长递增子序列+二分）

向右看齐 2024-03-27 09:26 56阅读 0赞

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

### 0. 题目 ###

给你一个二维整数数组  e n v e l o p e s envelopes envelopes ，其中  e n v e l o p e s \[ i \] = \[ w i , h i \] envelopes\[i\] = \[w\_i, h\_i\] envelopes\[i\]=\[wi,hi\] ，表示第  i i i 个信封的宽度和高度。

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

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

**注意**：不允许旋转信封。

示例 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

提示：

*   1 < = e n v e l o p e s . l e n g t h < = 1 0 5 1 <= envelopes.length <= 10^5 1<=envelopes.length<=105
 *   e n v e l o p e s \[ i \] . l e n g t h = = 2 envelopes\[i\].length == 2 envelopes\[i\].length==2
 *   1 < = w i , h i < = 105 1 <= w\_i, h\_i <= 105 1<=wi,hi<=105

### 1. 前序知识 ###

#### 1.1 二分 ####

还是来回顾一下二分法，虽然它很简单，但是很多时候临时让你写一个二分出来，还是会对

*  到底要给 `mid` 加一还是减一
 *  `while` 里到底用 `<=` 还是 `<`

产生疑问，然后调试个半天。这里给出三种二分搜索，基本包含了二分搜索的全部内容：

*  寻找一个数（基本的二分搜索）
 *  寻找左侧边界的二分搜索
 *  寻找右侧边界的二分搜索

##### 1.1.1 寻找一个数（基本的二分搜索） #####

int binarySearch(int[] nums, int target) {
        
    	int left = 0;
    	int right = nums.length - 1;  // 注意：区间为 [left, right]
        
    	while(left <= right) {
         // 最后为 left = right + 1
    		int mid = left + (right - left) / 2;
            if(nums[mid] == target) 
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1; 
    	}
        return -1;
    }

int binarySearch(int[] nums, int target) {
        
    	int left = 0;
    	int right = nums.length;  // 注意：区间为 [left, right)
        
    	while(left < right) {
         // 最后为 left == right
    		int mid = left + (right - left) / 2;
            if(nums[mid] == target) 
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid; 
    	}
        return -1;
    }

##### 1.1.2 寻找左侧边界的二分搜索 #####

int leftBound(int[] nums, int target) {
        
        if(nums.length == 0) 
            return -1;
    	int left = 0;
    	int right = nums.length;  // 注意：区间为 [left, right)
        
    	while(left < right) {
         // 最后为 left == right
    		int mid = left + (right - left) / 2;
            if(nums[mid] == target) 
                right = mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid; 
    	}
        // target 比所有数都大
        if(left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }

int leftBound(int[] nums, int target) {
        
        if(nums.length == 0) 
            return -1;
    	int left = 0;
    	int right = nums.length - 1;  // 注意：区间为 [left, right]
        
    	while(left <= right) {
         // 最后为 left = right + 1
    		int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
        
                right = mid - 1;
            } else if (nums[mid] < target) {
        
                left = mid + 1;
            } else if (nums[mid] > target) {
        
                right = mid - 1; 
            }
    	}
        // 检查出界情况
        if(left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }

##### 1.1.3 寻找右侧边界的二分搜索 #####

int rightBound(int[] nums, int target) {
        
        if(nums.length == 0) 
            return -1;
    	int left = 0;
    	int right = nums.length;  // 注意：区间为 [left, right)
        
    	while(left < right) {
         // 最后为 left == right
    		int mid = left + (right - left) / 2;
            if(nums[mid] == target) 
                left = mid + 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid; 
    	}
        if(left == 0 || nums[left-1] != target) 
            return -1;
        return left - 1;
    }

int rightBound(int[] nums, int target) {
        
        if(nums.length == 0) 
            return -1;
    	int left = 0;
    	int right = nums.length - 1;  // 注意：区间为 [left, right]
        
    	while(left <= right) {
         // 最后为 left = right + 1
    		int mid = left + (right - left) / 2;
            if(nums[mid] == target) 
                left = mid + 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1; 
    	}
        if(right < 0 || nums[right] != target) 
            return -1;
        return right;
    }

#### 1.2 最长递增子序列 ####

##### 1.2.1 动态规划解法 #####

相信大家对数学归纳法都不陌生，高中就学过，而且思路很简单。比如我们想证明一个数学结论，那么**我们先假设这个结论在 `k < n` 时成立，然后根据这个假设，想办法推导证明出 `k = n` 的时候此结论也成立**。如果能够证明出来，那么就说明这个结论对于 `k` 等于任何数都成立。

类似的，我们设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 `dp[0...i-1]` 都已经被算出来了，然后问自己：怎么通过这些结果算出 `dp[i]`？

直接拿最长递增子序列这个问题举例你就明白了。不过，首先要定义清楚 dp 数组的含义，即 `dp[i]` 的值到底代表着什么？

**我们的定义是这样的：`dp[i]` 表示以 `nums[i]` 这个数结尾的最长递增子序列的长度**。

int lengthOfLIS(int[] nums) {
        
        // 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        // base case：dp 数组全都初始化为 1
        Arrays.fill(dp, 1);
        for (int i = 0; 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);
            }
        }
        
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
        
            res = Math.max(res, dp[i]);
        }
        return res;
    }

##### 1.2.2 二分查找解法 #####

这个解法的时间复杂度为 `O(NlogN)`，但是说实话，正常人基本想不到这种解法（也许玩过某些纸牌游戏的人可以想出来）。所以大家了解一下就好，正常情况下能够给出动态规划解法就已经很不错了。

根据题目的意思，我都很难想象这个问题竟然能和二分查找扯上关系。其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关，甚至有一种排序方法就叫做 patience sorting（耐心排序）。

为了简单起见，后文跳过所有数学证明，通过一个简化的例子来理解一下算法思路。

首先，给你一排扑克牌，我们像遍历数组那样从左到右一张一张处理这些扑克牌，最终要把这些牌分成若干堆。

![在这里插入图片描述][7de9a4f79f9240e3895d3c30fb01cb71.png]

**处理这些扑克牌要遵循以下规则**：

只能把点数小的牌压到点数比它大的牌上；如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去；如果当前牌有多个堆可供选择，则选择最左边的那一堆放置。

比如说上述的扑克牌最终会被分成这样 5 堆（我们认为纸牌 A 的牌面是最大的，纸牌 2 的牌面是最小的）。

![在这里插入图片描述][d0cf66732ed9435ea8d47ca4f3cf24cd.png]

为什么遇到多个可选择堆的时候要放到最左边的堆上呢？因为这样可以保证牌堆顶的牌有序（2, 4, 7, 8, Q），证明略。

![在这里插入图片描述][1cc40297cd2d49fd8112414b4b02a02a.png]

按照上述规则执行，可以算出最长递增子序列，牌的堆数就是最长递增子序列的长度，证明略。

![在这里插入图片描述][66f1719bda7b4644b735a1dbb17f3176.png]

我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗，牌堆顶的牌不是**有序**吗，这就能用到二分查找了：用二分查找来搜索当前牌应放置的位置。

int lengthOfLIS(int[] nums) {
        
        int[] top = new int[nums.length];
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
        
            // 要处理的扑克牌
            int poker = nums[i];
    
            /***** 搜索左侧边界的二分查找 *****/
            int left = 0, right = piles;
            while (left < right) {
        
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
        
                    right = mid;
                } else if (top[mid] < poker) {
        
                    left = mid + 1;
                } else {
        
                    right = mid;
                }
            }
            /*********************************/
            
            // 没找到合适的牌堆，新建一堆
            if (left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }

### 2. 题解 ###

**这道题目其实是最长递增子序列的一个变种，因为每次合法的嵌套是大的套小的，相当于在二维平面中找一个最长递增的子序列，其长度就是最多能嵌套的信封个数**。

前面说的标准 LIS 算法只能在一维数组中寻找最长子序列，而我们的信封是由 `(w, h)` 这样的二维数对形式表示的，如何把 LIS 算法运用过来呢？

![在这里插入图片描述][96170275cca3415d8657c3399185fe66.png]

**先对宽度 `w` 进行升序排序，如果遇到 `w` 相同的情况，则按照高度 `h` 降序排序；之后把所有的 `h` 作为一个数组，在这个数组上计算 LIS 的长度就是答案**。

![在这里插入图片描述][1780378fc9ac4c6d81fa4cd077306040.png]

然后在 `h` 上寻找最长递增子序列，这个子序列就是最优的嵌套方案：

![在这里插入图片描述][377fcbbfd0144b70afc10cdc48150a64.png]

class Solution {
        
        public int maxEnvelopes(int[][] envelopes) {
        
            int len = envelopes.length;
            Arrays.sort(envelopes, new Comparator<int[]>() {
        
                public int compare(int[] a, int[] b) {
        
                    return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
                }
            });
            int[] height = new int[len];
            for(int i=0; i<len; i++) {
        
                height[i]=envelopes[i][1];
            }
            return lengthOfLIS(height);
        }
    
        public int lengthOfLIS(int[] nums) {
        
            int[] top = new int[nums.length];
            // 牌堆数初始化为 0
            int piles = 0;
            for (int i = 0; i < nums.length; i++) {
        
                // 要处理的扑克牌
                int poker = nums[i];
    
                /***** 搜索左侧边界的二分查找 *****/
                int left = 0, right = piles;
                while (left < right) {
        
                    int mid = (left + right) / 2;
                    if (top[mid] > poker) {
        
                        right = mid;
                    } else if (top[mid] < poker) {
        
                        left = mid + 1;
                    } else {
        
                        right = mid;
                    }
                }
                /*********************************/
                
                // 没找到合适的牌堆，新建一堆
                if (left == piles) piles++;
                // 把这张牌放到牌堆顶
                top[left] = poker;
            }
            // 牌堆数就是 LIS 长度
            return piles;     
        }
    }

![在这里插入图片描述][e03acb2828284446bedeb89b6a768061.png]

[LeetCode 354.]: https://leetcode.cn/problems/russian-doll-envelopes/
[7de9a4f79f9240e3895d3c30fb01cb71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4d9fbb8d3ec84b099168052a7a159eba.png
[d0cf66732ed9435ea8d47ca4f3cf24cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/14ab42c6a28744fcb37041ae65f7389d.png
[1cc40297cd2d49fd8112414b4b02a02a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ac033e5335f4441f82898dc7fb3be3e7.png
[66f1719bda7b4644b735a1dbb17f3176.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bc3c2314704646468ea04c97d7f6efa7.png
[96170275cca3415d8657c3399185fe66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/724c23614c694938a70eac33fe0e2643.png
[1780378fc9ac4c6d81fa4cd077306040.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bfa1c81a2c2f4928a9917284596e25d9.png
[377fcbbfd0144b70afc10cdc48150a64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/101c1061ffe240199a4d4a5cb314c6ad.png
[e03acb2828284446bedeb89b6a768061.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/365f177208af4af0b7719561a82de49b.png