聊一个有趣的问题，最长递增子序列。
1. 最长递增子序列的长度
即给定一个整数数组arr，找出数组中哪个子序列是严格递增的，且是最长的。返回它的长度。例如数组{1, 5, 2, 3, 4, -1}，它的最长子序列是1, 2, 3, 4，因此返回4。原题
方法1：动态规划
任何一个子序列都有一个末尾元素，我们定义这样的一个子问题$dp[i]$，表示必须以$arr[i]$作为子序列的末尾元素，$arr[0]..arr[i]$这段数组的最长递增子序列的长度，假设数组长度为$len$，那么显然$max{dp[0],dp[1],…,dp[len-1]}$就是原问题的解。那么怎么求解$dp[i]$呢？
首先当$i=0$的时候，此时数组中只有一个数，因此最长递增子序列长度是1，即$dp[0]=1$；
当$i>0$的时候，我们考察$dp[0]..dp[i-1]$，需要在$arr[0]..arr[i-1]$范围内找哪些数小于$arr[i]$，对于那些小于$arr[i]$的数，因为它们排在$arr[i]$的前面，$arr[i]$都可以排在他们后面形成更长的递增子序列，即我们需要找到一个位置$j \in [0, i-1],arr[j]<arr[i]$使得$dp[j]$最大。那么此时$dp[i]=dp[j]+1$。如果我们找不到一个满足条件的位置$j$，那么$dp[i]=1$。
注意我们定义子问题的$dp[i]$的时候，为什么要求$arr[i]$必须作为末尾？
因为只有这样定义子问题，我们才能根据曾经求解过的$dp[0]..dp[i]$，来加工得到未知的子问题$dp[i+1]$的解。如果我们把子问题$dp[i]$定义为数组$arr[0]..arr[i]$的最长递增子序列的长度的话，我们发现当我们求解$dp[i+1]$的时候，因为我们只知道$arr[0]..arr[i]$最长递增子序列的长度是多少，没有末尾元素的信息，我们就求不到$dp[i+1]$的答案了。因此使用动态规划求解问题的时候，一定要注意子问题的设计。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class LongestIncreasingSubSeqDp {
public static int lis(int[] arr) {
int len = 0, ans = 1;
if(arr == null || (len = arr.length) < 2) return len;
int[] dp = new int[len];
dp[0] = 1;
for(int i = 1; i < len; ++i) {
dp[i] = 1;
for(int j = 0; j < i; ++j) {
if(arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
|
时间复杂的$O(N^2)$，空间复杂度$O(N)$。下面介绍一种更省时间的方法。
方法2：贪心+二分（最优解）
这个贪心的思路是，如果想让递增子序列更长，那么我们一定要让子序列增长的“慢”一些。啥意思呢？例如在数组{0, 100_0000, 2, -1, 1, 3}中，我们发现了递增子序列{0, 100_0000}，他的长度是2；我们继续往后遍历发现，2也能排在1的后面，形成长度为2的递增子序列。即对于长度为2的递增子序列来说，现在有两个末尾可以选择，那么我们一定要选取2而不是100_0000；因为2使得这个递增子序列增长的最慢，即对于递增子序列{0, 100_0000}和{0, 2}来说，后面的3，可以放在{0, 2}的后面形成更长的递增子序列，而{0, 100_0000}不行。所以选择更小的末尾，不会让已经发现的递增子序列错过形成更长的递增子序列的可能性。
因此我们关注的一个点就是某个长度的递增子序列的最小末尾。当我们发现某个元素比最长的递增子序列的最小末尾还大的时候，那么这个元素就可以放在这个最长的递增子序列后面，形成更长的递增子序列；如果这个元素不大于最长的递增子序列的最小末尾，那么我们看它能作为哪一个长度的递增子序列的更小的末尾，然后更新它。如下图所示：
在遍历的过程中，我们使用一个变量维护当前发现的最长的递增子序列的长度。
不难发现，minTail这个数组是递增的，即递增子序列越长，它的最小末尾也越大。
证明递增性质：
假设minTail数组不是递增，那么一定存在两个位置$i<j$，且$minTail[i] \geq minTail[j]$，那么我们取长度为$j$的递增子序列中的前$i$个元素，构成的一个新的长度为$i$的递增子序列，那么这个递增子序列的末尾元素$tail_i$一定小于$minTail[j]$，同样小于$minTail[i]$，即我们发现了长度为$i$的递增子序列的一个更小的末尾，这个结论和$minTail[i]$是长度为$i$的递增子序列的最小末尾的假设前提矛盾。因此minTail数组递增。
当我们遍历到一个新的元素$x$，发现$x$没有比目前已知的最长的递增子序列的最小末尾大的时候，那么此时$x$一定可以成为某个长度的递增子序列的一个更小的末尾，我们需要找到这个末尾然后用$x$去更新这个末尾。
举个例子，假设某一时刻minTail数组是这样的，{1,2,4,6}，此时我们遍历到数$3$，显然这个3没有6大，
- 那么这个3可以更新6吗？不行，虽然3比6小，但是长度为3的递增子序列的最小末尾是4，长度为4的递增子序列的最小末尾不可能比4小；
- 那么这个3可以更新4吗？可以，3可以成为长度为3的递增子序列的一个更小的末尾，并且更新后不会打破minTail数组递增的性质；
$x$要更新哪一个末尾呢？首先需要明确一点就是，被$x$更新的末尾，一定是不会比$x$更小（因为minTail数组记录的是最小末尾），所以需要被$x$更新的末尾，一定是minTail在数组中，从左往右遍历第一个不小于$x$的那个末尾。在一个有序的数组中，找到第一个不小于$x$的元素，使用二分查找在$\log_2N$时间复杂度内就可以解决。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public class LongestIncreasingSubSeqGreedy {
public static int lis(int[] arr) {
int len = 0;
if(arr == null || (len = arr.length) < 2) return len;
int[] minTail = new int[len];
minTail[0] = arr[0];
int i = 1, j = 0;
for(; i < len; ++i) {
if(arr[i] > minTail[j]) minTail[++j] = arr[i];
else if(arr[i] < minTail[j]) minTail[getUpdateIndex(minTail, j, arr[i])] = arr[i];
}
return j + 1;
}
static int getUpdateIndex(int[] arr, int bound, int target) {
int lo = 0, hi = bound, m;
while(lo < hi) {
m = (lo + hi) >>> 1;
if(arr[m] < target) lo = m + 1;
else hi = m;
}
return lo;
}
}
|
时间复杂度$O(N\log_2N)$，空间复杂度$O(N)$。
2. 最长递增子序列的个数
这个问题在原问题的基础上，还要求有几个最长递增子序列，返回个数。原题
方法1：动态规划
在上述使用动态规划求解最长递增子序列的过程中，我们使用一个数组$dp$来存储各个子问题的答案，且$dp[i]$表示必须以$arr[i]$作为子序列的末尾的时候，最长递增子序列的长度。我们可以在设置一个计数数组$cnt$，$cnt[i]$表示必须以$arr[i]$作为子序列的末尾的时候，最长递增子序列的个数。并使用一个变量$maxIsLen$维护最长的递增子序列的长度。
当$i=0$的时候，$dp[i]=1,cnt[i]=1$；
当$i>0$的时候，初始化$dp[i]=1,cnt[i]=1$，我们遍历$j \in [0,i-1]$，在保证$arr[j]<arr[i]$的情况下，
2.1. 如果$dp[j]+1 > dp[i]$，即此时我们发现了一个更长的自增子序列，那么长度和数量都更新，$dp[i]=dp[j]+1,cnt[i]=cnt[j]$
2.2. 否则如果$dp[j]+1=dp[i]$，即说明我们找到了相同长度的递增子序列，那么$dp[i]$不变，$cnt$累加，$cnt[i]+=cnt[j]$。
最后我们需要遍历$dp$数组，找出所有的$dp[i]=maxIsLen$，把它们的$cnt[i]$累加到答案中。
根据上面的逻辑，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public class LongestIncreasingSubSeqNumberDP {
public static int numberOfLis(int[] arr) {
int len = 0;
if(arr == null || (len = arr.length) < 2) return len;
int[] dp = new int[len], cnt = new int[len];
dp[0] = cnt[0] = 1;
int i = 1, j, maxIsLen = 1, ans = 0;
for(; i < len; ++i) {
dp[i] = cnt[i] = 1;
for(j = 0; j < i; ++j) {
if(arr[j] < arr[i]) {
if(dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
}else if(dp[j] + 1 == dp[i]) {
cnt[i] += cnt[j];
}
}
}
maxIsLen = Math.max(maxIsLen, dp[i]);
}
for(i = 0; i < len; ++i) {
if(dp[i] == maxIsLen) ans += cnt[i];
}
return ans;
}
}
|
方法2：贪心+二分（最优解）
这个方法是基于求解长度的时候的二分+贪心的做法，在上面的解法中，我们使用了一个数组$minTail$来记录任何一个长度的递增子序列的最小末尾，在遍历的数组的时候，不断的更新每个长度的递增子序列的最小末尾。如果要求解最长递增子序列的个数，我们在遇到更小的末尾的时候，就不能更新了，需要把在遍历过程中，任何长度的递增子序列的所有出现的末尾，记录下来。
原来的$minTail[i]$表示长度为$i+1$的递增子序列的最小末尾，现在使用$minTail[i][j]$来表示，当前所发现的长度为$i+1$的递增子序列的第$j$个末尾，我们把更新末尾的操作，变成了把更小的末尾加入$minTail[i]$列表的操作。在上面求解长度的时候，因为只有遇到更小的末尾或者相同的末尾的时候才会发生更新操作，因此可以知道$minTail[i]$列表是非增的。
现在我们记录下所有的末尾了，还需要记录当$minTail[i][j]$作为长度为$i+1$的递增子序列的最小末尾的时候，此时长度为$i+1$的递增子序列有几个，这个量我们使用$cnt[i][j]$来记录。那么$cnt[i][j]$如何得到呢？此时我们就需要考察$cnt[i-1]$数组和$minTail[i-1]$数组了，我们需要遍历$minTail[i-1]$数组，对于$x \in [0, minTail[i-1].length-1]$，如果满足$minTail[i-1][x]<minTail[i][j]$，那么我们就把$cnt[i-1][x]$累加到$cnt[i][j]$中去。如下图所示：
$cnt$中最后一个数组的累加和就是答案。根据这个逻辑，可以写出代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| public class LongestIncreasingSubSeqNumberGreedy {
public static int numberOfLis(int[] arr) {
int len = 0;
if(arr == null || (len = arr.length) < 2) return len;
ArrayList<ArrayList<Integer>> minTail = new ArrayList<>(), cnt = new ArrayList<>();
minTail.add(newListWith(arr[0]));
cnt.add(newListWith(1));
int i = 1;
for(; i < len; ++i) {
if(arr[i] > lastOf(lastOf(minTail))) {
cnt.add(newListWith(getCnt(lastOf(minTail), lastOf(cnt), arr[i])));
minTail.add(newListWith(arr[i]));
}else {
int addIndex = getAddIndex(minTail, arr[i]);
minTail.get(addIndex).add(arr[i]);
cnt.get(addIndex).add(addIndex > 0 ? getCnt(minTail.get(addIndex - 1), cnt.get(addIndex - 1), arr[i]) : 1);
}
}
int ans = 0;
ArrayList<Integer> lastCnt = lastOf(cnt);
for(i = 0, len = lastCnt.size(); i < len; ++i) {
ans += lastCnt.get(i);
}
return ans;
}
static int getCnt(ArrayList<Integer> tails, ArrayList<Integer> cnt, int target) {
int ans = 0;
for(int i = 0, len = tails.size(); i < len; ++i) {
if(tails.get(i) < target) ans += cnt.get(i);
}
return ans;
}
static int getAddIndex(ArrayList<ArrayList<Integer>> arr, int target) {
int lo = 0, hi = arr.size() - 1, m;
while(lo < hi) {
m = (lo + hi) >>> 1;
if(lastOf(arr.get(m)) < target) lo = m + 1;
else hi = m;
}
return lo;
}
static ArrayList newListWith(int val) {
ArrayList<Integer> ans = new ArrayList<>();
ans.add(val);
return ans;
}
static <T> T lastOf(ArrayList<T> list) {
return list.get(list.size() - 1);
}
}
|
看到这里，你已经了解了这个方法的思想了，但是还有一个需要优化的地方，就是我们的getCnt方法。它在计算当前的个数的时候，需要遍历上一步的$minTail$数组。这是一个比较耗时的操作。我们知道同样长度的递增子序列的最小末尾是不增的，即有序的。因此当我们遍历$minTail[pre]$到某个位置$index$的时候，发现$minTail[pre][index]$小于当前末尾$arr[i]$，那么$minTail[pre]$中$index$后面的直到结尾的所有元素都是小于$arr[i]$的。即我们的$cnt[current][]=cnt[pre][index]+cnt[pre][index+1]+…+cnt[pre][cnt[pre].length-1]$。
可见是在$minTail[pre]$中找到第一个小于$arr[i]$的位置，然后从这个位置到结尾的$cnt[pre]$的累加和。那么我们可以把$cnt$数组中的值做成前缀和的形式，并根据$minTail[pre]$数组的有序性，我们可以使用二分查找算法，找到$minTail[pre]$中最后一个不小于$arr[i]$的位置$lastNotLessIndex$，那我们的$cnt[current][]=cnt[pre][cnt[pre].length-1]-cnt[pre][lastNotLessIndex]+cnt[current][last]$，这里的$cnt[current][last]$是$cnt[current][]$的前一个元素。
那么最后的答案就是$cnt$数组中最后一个数组的最后一个元素的值。优化后的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| public class LongestIncreasingSubSeqNumberGreedy2 {
public static int numberOfLis(int[] arr) {
int len = 0;
if(arr == null || (len = arr.length) < 2) return len;
ArrayList<ArrayList<Integer>> minTail = new ArrayList<>(), cnt = new ArrayList<>();
minTail.add(newListWith(arr[0]));
cnt.add(newListWith(1));
int i = 1;
for(; i < len; ++i) {
if(arr[i] > lastOf(lastOf(minTail))) {
cnt.add(newListWith(getCnt(lastOf(minTail), lastOf(cnt), arr[i])));
minTail.add(newListWith(arr[i]));
}else {
int addIndex = getAddIndex(minTail, arr[i]);
minTail.get(addIndex).add(arr[i]);
cnt.get(addIndex).add((addIndex > 0 ? getCnt(minTail.get(addIndex - 1), cnt.get(addIndex - 1), arr[i]) : 1) + lastOf(cnt.get(addIndex)));
}
}
return lastOf(lastOf(cnt));
}
static int getCnt(ArrayList<Integer> tails, ArrayList<Integer> cnt, int target) {
int lo = -1, hi = tails.size() - 2, m;
while(lo < hi) {
m = (lo + hi + 1) >>> 1;
if(tails.get(m) < target) hi = m - 1;
else lo = m;
}
return lastOf(cnt) - (lo == -1 ? 0 : cnt.get(lo));
}
static int getAddIndex(ArrayList<ArrayList<Integer>> arr, int target) {
int lo = 0, hi = arr.size() - 1, m;
while(lo < hi) {
m = (lo + hi) >>> 1;
if(lastOf(arr.get(m)) < target) lo = m + 1;
else hi = m;
}
return lo;
}
static ArrayList newListWith(int val) {
ArrayList<Integer> ans = new ArrayList<>();
ans.add(val);
return ans;
}
static <T> T lastOf(ArrayList<T> list) {
return list.get(list.size() - 1);
}
}
|
时间复杂度$O(N\log_2{N})$，空间复杂度$O(N)$。
3. 找出所有的最长递增子序列
问题再次升级，不但需要知道有几个最长递增子序列，还要找出所有的最长递增子序列（使用下标表示）。例如arr={1, 2, 30, 40, 0, 2, 3, 4, -2, 5}，它有三个最长递增子序列，他们是[[4, 5, 6, 7, 9], [0, 5, 6, 7, 9], [0, 1, 6, 7, 9]]。
方法1：动态规划
基于最初的动态规划，我们在求解$dp[i]$的时候，不但需要求解出$cnt[i]$，还需要记录$arr[i]$是拼到哪些数的后面， 形成了更长的递增子序列，记录这些数在数组中的下标。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| public class FindAllLongestIncreasingSubSeqDP {
public static int[][] findAll(int[] arr) {
int len = 0;
if(arr == null || (len = arr.length) == 0) return null;
if(len == 1) return new int[1][1];
int[] dp = new int[len], cnt = new int[len];
ArrayList<LinkedList<Integer>> record = new ArrayList<>(len);
record.add(null);
dp[0] = cnt[0] = 1;
int i = 1, j, maxLen = 1;
for(; i < len; ++i) {
dp[i] = cnt[i] = 1;
record.add(null);
for(j = 0; j < i; ++j) {
if(arr[j] < arr[i]) {
if(dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
LinkedList<Integer> rcd = record.get(i);
if(rcd == null) rcd = newListWith(j);
else {
rcd.clear();
rcd.add(j);
}
record.set(i, rcd);
}else if(dp[j] + 1 == dp[i]) {
cnt[i] += cnt[j];
record.get(i).add(j);
}
}
}
maxLen = Math.max(maxLen, dp[i]);
}
int maxCnt = 0;
for(i = 0; i < len; ++i) {
if(dp[i] == maxLen) maxCnt += cnt[i];
}
int[][] ans = new int[maxCnt][maxLen];
j = 0;
for(i = 0; i < len; ++i) {
if(dp[i] == maxLen) {
fillAns(ans, j, maxLen - 1, cnt, arr, record, i);
j += cnt[i];
}
}
return ans;
}
static void fillAns(int[][] ans, int row, int col, int[] cnt, int[] arr, ArrayList<LinkedList<Integer>> record, int index) {
int i = 0;
for(; i < cnt[index]; ++i) ans[row + i][col] = index;
if(col == 0) return;
LinkedList<Integer> pres = record.get(index);
i = 0;
for(int pre: pres) {
fillAns(ans, row + i, col - 1, cnt, arr, record, pre);
i += cnt[pre];
}
}
static LinkedList newListWith(int val) {
LinkedList<Integer> ans = new LinkedList<>();
ans.add(val);
return ans;
}
}
|
方法2：贪心+二分
基于上面的二分做法，我们在求$cnt[i][j]$的时候，我们需要参考$minTail[i-1][]$和$cnt[i-1][]$，需要在$minTail[i-1][]$中找出哪些末尾是小于$minTail[i][j]$的，然后把其数量加入$cnt[i][j]$。具体求解的时候，我们使用了前缀和+二分法的做法，降低了时间复杂度。为了求出所有的递增子序列，我们的$minTail$数组不能直接存最小的末尾，而是存这个末尾在原数组中的下标；并且还需要存储在求解$cnt[i][j]$的时候，$minTail[i-1][]$中哪些末尾是小于$minTail[i][j]$的，由于$minTail$的有序性，我们可以只存一个范围。
当我们遍历数组，求解得到$minTail$和$cnt$的时候，我们需要再次根据每一步的决策，反推回去，填充答案数组。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| public class FindAllLongestIncreasingSubSeqGreedy {
public static int[][] findAll(int[] arr) {
int len = 0;
if(arr == null || (len = arr.length) == 0) return null;
if(len == 1) return new int[1][1];
ArrayList<ArrayList<Info>> infos = new ArrayList<>();
infos.add(newListWith(new Info(0, 1)));
int i = 1;
for(; i < len; ++i) {
ArrayList<Info> lastInfoList = lastOf(infos);
Info lastInfoNode = lastOf(lastInfoList);
if(arr[i] > arr[lastInfoNode.tailIndex]) {
int notLessThanIndex = getLastNotLessIndex(lastInfoList, arr[i], arr);
infos.add(newListWith(new Info(
i,
lastInfoNode.cnt - (notLessThanIndex == -1 ? 0 : lastInfoList.get(notLessThanIndex).cnt),
notLessThanIndex + 1,
lastInfoList.size() - 1
)));
}else {
int addIndex = getAddIndex(infos, arr[i], arr);
ArrayList<Info> indexedInfo = infos.get(addIndex);
if(addIndex == 0) indexedInfo.add(new Info(i, lastOf(indexedInfo).cnt + 1));
else {
ArrayList<Info> preInfo = infos.get(addIndex - 1);
int notLessThanIndex = getLastNotLessIndex(preInfo, arr[i], arr);
indexedInfo.add(new Info(
i,
lastOf(preInfo).cnt - (notLessThanIndex == -1 ? 0 : preInfo.get(notLessThanIndex).cnt) + lastOf(indexedInfo).cnt,
notLessThanIndex + 1,
preInfo.size() - 1
));
}
}
}
int maxLen = infos.size(), cnt = lastOf(lastOf(infos));
int[] ans = new int[cnt][maxLen];
i = 0;
int j = 0;
for(Info inff: lastOf(infos)) {
fillAns(ans, i, maxLen - 1, infos, maxLen - 1, j);
i += inff.cnt - (j == 0 ? 0 : lastOf(infos).get(j - 1).cnt);
++j;
}
return ans;
}
static void fillAns(int[][] ans, int row, int col, ArrayList<ArrayList<Info>> infos, int x, int y) {
int i = 0, j = col;
ArrayList<Info> infoList = infos.get(x);
Info inf = infoList.get(y);
int cnt = inf.cnt - (y == 0 ? 0 : infoList.get(y - 1).cnt);
for(; i < cnt; ++i) arr[row + i][col] = inf.tailIndex;
if(col == 0) return;
ArrayList<Info> preList = infos.get(x - 1);
i = 0;
for(int m = inf.l; m <= inf.r; ++m) {
fillAns(ans, row + i, col - 1, infos, x - 1, m);
i += preList.get(m).cnt - (m == 0 ? 0 : preList.get(m - 1).cnt);
}
}
static int getAddIndex(ArrayList<ArrayList<Info>> infos, int target, int[] arr) {
int lo = 0, hi = infos.size() - 1, m;
while(lo < hi) {
m = (lo + hi) >>> 1;
if(arr[infos.get(m).tail] < target) lo = m + 1;
else hi = m;
}
return lo;
}
static int getLastNotLessIndex(ArrayList<Info> info, int target, int[] arr) {
int lo = -1, hi = info.size() - 2, m;
while(lo < hi) {
m = (lo + hi + 1) >>> 1;
if(arr[info.get(m).tail] < target) hi = m - 1;
else lo = m;
}
return lo;
}
static ArrayList newListWith(Info inf) {
ArrayList<Info> list = new ArrayList<>();
list.add(inf);
return list;
}
static <T> T lastOf(ArrayList list) {
return list.get(list.size() - 1);
}
static class Info {
int tailIndex, cnt, l, r;
Info(int t, int c) {
tailIndex = t;
cnt = c;
l = -1;
}
Info(int t, int c, int ll, int rr) {
tailIndex = t;
cnt = c;
l = ll;
r = rr;
}
}
}
|
4. 相关题目
俄罗斯套娃问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 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 <= envelopes.length <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105
我们把envelopes按照其宽度从小到大排序（相同宽度的按照其高度从大到小排序），排好序后，我们求这个数组其高度纬度上的最长递增子序列的长度，即为答案。
为啥呢？
这个问题的本质是让我们找出最长的一个信封序列，假设长度为$len$，$[[a_1,b_1],[a_2,b_2],…,[a_{len},b_{len}]]$，那么必有：
$$
a_1<a_2<…<a_{len},b_1<b_2<…<b_{len}
$$
成立，即信封的宽度和高度都严格递增。我们首先固定一个变量，不妨固定宽度。我们把envelopes按照宽度从小到大排序得到$sortedEnvelopes$，那么显然，答案必定是$sortedEnvelopes$的一个子序列。
现在问题转化为了我们需要在$sortedEnvelopes$中找到一个最长的子序列，满足信封的高度是严格递增的。此时不要忘记，我们找到的子序列中不能包含宽度相同的信封，因为宽度相同的信封不能套娃。为了避免找到的递增子序列中的宽度相同，在当初给信封的宽度排序的时候，对于宽度相同的信封，按照其高度从大到小的顺序排列。这样我们找到的高度纬度上的最长递增子序列中，宽度不可能相同。
那么原问题本质上就是一个数组上的最长递增子序列问题。
