4.俄罗斯套娃信封问题

leetcode354题
给你⼀个⼆维整数数组 envelopes，其中 envelopes[i] = [wi, hi]，表示第 i 个信封的宽度和⾼度。

当另⼀个信封的宽度和⾼度都⽐这个信封⼤的时候，这个信封就可以放进另⼀个信封⾥，如同俄罗斯套娃⼀样。

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

解题思路：我们知道最长递增子序列在一维数组里面求元素的最长递增子序列，本题相当于在二维平面求最长递增子序列。先对宽度进行升序排序，如果宽度相同，按照高度降序排序，然后对高度进行最长递增子序列
如下图所示
 

 

```java
public static int maxEnvelopes(int[][] envelopes){int n=envelopes.length;//行数//按宽度升序排序，如果宽度一样，则按高度降序排列Arrays.sort(envelopes, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0]==o2[0]?o2[1]-o1[1]: o1[0]-o2[0];}});//对高度数组寻找最长递增子序列（LIS）int[] height=new int[n];for(int i=0;i<n;i++){height[i]=envelopes[i][1];}return lengthOfLIS(height);}//返回nums中LIS的长度private static int lengthOfLIS(int[] nums) {int piles=1, n=nums.length;int [] top=new int[n];top[0]=nums[0];for(int i=1;i<n;i++){int poker=nums[i];int left=0,right=piles-1;//二分法右边界搜索while(left<=right) {int mid = (left + right) / 2;if (top[mid] >= poker)right = mid-1;elseleft = mid + 1;}if (left >=piles) {piles++;}top[left] = poker;}return piles;
}
```

这道题主要的问题是解决最长递增子序列(LIS)问题，我在这用一个很简单的例子介绍下算法原理，假设序列为[3,4,7,5]，第一步我们开辟一个长度为n的top放最长子序列，变量piles是top中最长子序列的长度。
第一步，将3放入top中，piles=1；
第二步，遍历4，7，3。等于4时，对top中的最长子序列（3）进行二分右边界查找，区间为[0,piles-1]由上文可知，当目标值大于最长子序列中的最大的数，二分查找返回的值left》piles，此时就可以将4添加到top中，piles+1。
第三步，7>4同理，top=[3,4,7]，piles=3。
第四步，target=5返回的值是7对应的索引，此时用target的值取代7，top=[3,4,5],piles=3。

至此这道俄罗斯套娃信封困难题我们已经解决了，从解题的基本思路来看，就是一道LIS问题，但本题的难点是如何将套娃问题分解成LIS问题。

出题方往往想考的是如何使用二叉搜索算法解决实际问题，在这方面没有任何诀窍，只有多见识。我们首先要做的是能闭着眼睛写二叉搜索的三种形式。

5.判断子序列

leetcode392题
要求：给定字符串s和t，判断s是否为t的⼦序列。
简单解法：利用双指针i，j分别指向s，t，一边前进一边匹配。

```Java
public static boolean isSubsequence(String s, String t){int i=0,j=0;//双指针while(i<s.length()&&j<t.length()){if(s.charAt(i)==t.charAt(j)){i++;}j++;}return i==s.length();}
```

进阶解法：当匹配序列s过多，每一次匹配时间复杂度O(n)，怎么才能缩短匹配时间呢？

基本思路：
1. 将字符串t中的每一个字母按顺序记下索引位置，比如a出现的位置有[0,4,7]，一直到z，如果没有出现就为null；
2. 遍历字符串s中的每一个字母，去对应t字符串字母索引中比target值大的索引，target值是上一个字母匹配对应的索引加1，初始值设置为零。保证匹配按照顺序进行。

对t进行预处理，将t中字母的索引放入index中，时间复杂度O(n)。运用二分查找，可以将时间复杂度降低，大约是 O(MlogN)，M 为 s 的长度。由于 N 相对 M 大很多，所以后者效率会更高。
 

```Java
public static boolean isSubsequence1(String s, String t){int m=s.length(),n=t.length();//对t进行预处理，将t中字母的索引放入index中，时间复杂度O(n)ArrayList<Integer>[] index=new ArrayList[256];for(int i=0;i<n;i++){char c=t.charAt(i);if(index[c]==null)index[c]=new ArrayList<>();index[c].add(i);}int target=0;for(int i=0;i<m;i++){char cs=s.charAt(i);//该字母不在t中if(index[cs]==null)return false;//将list集合转换成数组，如果左边界参数用的是集合不用转int[] nums=new int[index[cs].size()];for(int j=0;j<index[cs].size();j++){nums[j]=index[cs].get(j);System.out.println(nums[j]);}int pos=leftBound(nums,target);//target大于搜索区间最大值if(pos==index[cs].size())return false;//为什么要+1呢？ 想想如果s中有两个aa连着，如果第一个a匹配的索引是4，第二个a会重复匹配target=index[cs].get(pos)+1;}return true;}
```