354. 俄罗斯套娃信封问题
https://leetcode-cn.com/problems/russian-doll-envelopes/
算法分析
首先我们从两种情况来讨论这个问题:
- w无重复值（即信封的宽度每个信封都不一样）
- w可以重复（即信封的宽度存在一样的，题目就是这种情况）
针对情况I
当每个信封的宽度和高度不一样时，我们可以对信封按照宽度从小到大进行排序，比如针对信封[[3,2],[2, 4],[4,3],[5, 6],[6,5]排序后变为
w: 2 -> 3 -> 4 -> 5 -> 6
h: 4 -> 2 -> 3 -> 6 -> 5
此时，因为信封的宽度w已经是从小到大排列了，要想信封可以套，这要求关于信封高度h的数组[4, 2, 3, 6, 5]是的子序列是递增的，且要求是最长的（题目要求的是最多的信封），所以可以转化为另一个问题：给定数组，求它的最长递增子序列（也称最长上升子序列）。关于这个问题在leetcode300有具体描述。
针对情况Ⅱ
对于情况Ⅱ，我们首先像情况I一样考虑，对信封的宽度w按从小到大排序，那么此时面临一个问题，对于相同宽度的信封的高h怎么进行排序，如果我们也按照从小到大排序，那么此时按照信封高求出来的最长递增子序列有可能存在宽度w相同的情况。
举个栗子：
当宽度w = 1时， 此时有3个信封，h = 2, 3, 4
当宽度w = 2时，此时有两个信封，h = 3, 6
按照上面的排序方式排序后，
w: 1 -> 1 -> 1 -> 2 -> 2
h: 2 -> 3 -> 4 -> 3 -> 6
此时数组h的最长递增子序列为[2, 3, 4, 6]显然不符合条件。所以这种排序方式是错误的。
那么正确的排序方式是什么样的呢，就是当w相同时，h逆序，从大到小排列，这样你可以想一下，针对h求出来的最长递增子序列不会存在w相等，而h递增的情况，因为w相同的时候，右边的数总是小于等于左边的数，不会出现在最长递增子序列里面。
还是上面那个栗子排序后：
w: 1 -> 1 -> 1 -> 2 -> 2
h: 4 -> 3 -> 2 -> 6 -> 3
此时数组h的最长递增子序列长度为2（[4, 6]或[3, 6]或者其他），即最多有两个信封可以套。
1 //二维数组排序
2 type pair struct{
3 x int
4 y int
5 }
6
7 type Type []pair
8
9 func (t Type) Len() int{
10 return len(t)
11 }
12
13 func (t Type) Less(i,j int) bool{
14 if t[i].x < t[j].x {
15 return true
16 }else if t[i].x > t[j].x{
17 return false
18 }else{
19 //相同x值，逆序
20 return t[i].y > t[j].y
21 }
22 }
23
24 func (t Type) Swap(i,j int) {
25 t[i],t[j] = t[j],t[i]
26 }
27
28
29 func maxEnvelopes(envelopes [][]int) int {
30 n := len(envelopes)
31 if n<= 1{
32 return n
33 }
34 var p Type
35 for i:=0;i<n;i++{
36 p = append(p,pair{envelopes[i][0],envelopes[i][1]})
37 }
38 sort.Sort(p)
39 var h []int
40 for i:=0;i<n;i++{
41 h = append(h,p[i].y)
42 }
43 //对h数组进行LIS
44 return LIS(h)
45 }
46 func MAX(i,j int) int{
47 if i<j{
48 return j
49 }else{
50 return i
51 }
52 }
53 //2 3 5 1 3 4
54 func LIS(h []int) int{
55 n := len(h)
56 dp := make([]int,n)
57 dp[0] = 1
58 res := 0
59 for i:=1;i<n;i++{
60 m := 0
61 for j:=0;j<i;j++{
62 if h[j] < h[i]{
63 m = MAX(m,dp[j])
64 }
65 dp[i] = m+1
66 }
67 res = MAX(dp[i],res)
68 }
69 return res
70 }
优化1、排序优化 2、LIS算法优化
排序直接对[][]int数组进行排序
type Env [][]intfunc (e Env) Len() int{
return len(e)
}func (e Env) Less(i,j int) bool{
if e[i][0] == e[j][0]{
return e[i][1] > e[j][1]
}
return e[i][0] < e[j][0]
}func (e Env) Swap(i,j int) {
e[i],e[j] = e[j],e[i]
}func maxEnvelopes(envelopes [][]int) int {
n := len(envelopes)
if n<= 1{
return n
}
sort.Sort(Env(envelopes))
var h []int
for i:=0;i<n;i++{
h = append(h,envelopes[i][1])
}
//对h数组进行LIS
return LIS(h)
}
func MAX(i,j int) int{
if i<j{
return j
}else{
return i
}
}
//实际上逻辑是这样: 数组nums中的数nums[i]在 ends数组中二分查找第一个比他大的数并替换，若没有找到，则将nums[i]加在ends末尾，并且dp[i]=ends里面arr[i]的下标+1。
func LIS(nums []int) int{
n := len(nums)
if n<= 1{
return n
}
dp := make([]int,n)
//这里有个go 切片的隐藏bug。一开始ends := make([]int,n)了，这样的话，ends = append(ends,nums[i])是从第n+1个开始append
//这里非常容易出错，因为right = len(ends）-1这个大坑。
//这里可以变换下：right = max(left,right).
ends := make([]int,1)
dp[0] = 1
ends[0] = nums[0]
res := 0
for i:=1;i<n;i++{
left , right := 0,len(ends)-1
for left <= right{
m := left+(right-left)/2
if ends[m] < nums[i]{
left = m+1
}else{
right = m-1
}
}
if left < len(ends) && ends[left] >= nums[i]{
ends[left] = nums[i]
}else{
ends = append(ends,nums[i])
}
dp[i] = left+1
res = MAX(res,dp[i])
}
return res
}
