Skip to content

Commit c079fa8

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0354
No.0354.Russian Doll Envelopes
1 parent b77d7bd commit c079fa8

File tree

8 files changed

+294
-82
lines changed

8 files changed

+294
-82
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -68,7 +68,7 @@
6868
- [摘樱桃 II](/solution/1400-1499/1463.Cherry%20Pickup%20II/README.md) - 线性 DP、数字三角形模型
6969
- [最长递增子序列](/solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md) - 线性 DP、最长上升子序列模型
7070
- [删列造序 III](/solution/0900-0999/0960.Delete%20Columns%20to%20Make%20Sorted%20III/README.md) - 线性 DP、最长上升子序列模型
71-
71+
- [俄罗斯套娃信封问题](/solution/0300-0399/0354.Russian%20Doll%20Envelopes/README.md) - 线性 DP、最长上升子序列模型、贪心优化
7272

7373
### 4. 高级数据结构
7474

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
6767
- [Cherry Pickup II](/solution/1400-1499/1463.Cherry%20Pickup%20II/README_EN.md) - Linear problem
6868
- [Longest Increasing Subsequence](/solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md) - Linear problem, LIS
6969
- [Delete Columns to Make Sorted III](/solution/0900-0999/0960.Delete%20Columns%20to%20Make%20Sorted%20III/README_EN.md) - Linear problem, LIS
70+
- [Russian Doll Envelopes](/solution/0300-0399/0354.Russian%20Doll%20Envelopes/README_EN.md) - Linear problem, LIS
7071

7172
### 4. Advanced Data Structures
7273

‎solution/0300-0399/0354.Russian Doll Envelopes/README.md

Lines changed: 99 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -43,9 +43,11 @@
4343

4444
<!-- 这里可写通用的实现逻辑 -->
4545

46-
排序 + [最长递增子序列](/solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)。
46+
按 w 进行升序排序，若 w 相同则按 h 降序排序。然后问题转换为求 h 数组的最长递增子序列长度。参考 [300. 最长递增子序列](/solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)。
4747

48-
按 w 进行升序排序，若 w 相同则按 h 降序排序。然后问题转换为求 h 数组的最长递增子序列长度。
48+
**方法一：贪心 + 二分查找**
49+
50+
时间复杂度 O(nlogn)。
4951

5052
<!-- tabs:start -->
5153

@@ -56,19 +58,17 @@
5658
```python
5759
class Solution:
5860
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
59-
if not envelopes:
60-
return 0
6161
envelopes.sort(key=lambda x: (x[0], -x[1]))
62-
nums = [x[1] for x in envelopes]
63-
n = len(nums)
64-
dp = [1] * n
65-
res = 1
66-
for i in range(1, n):
67-
for j in range(i):
68-
if nums[j] < nums[i]:
69-
dp[i] = max(dp[i], dp[j] + 1)
70-
res = max(res, dp[i])
71-
return res
62+
d = [envelopes[0][1]]
63+
for _, h in envelopes[1:]:
64+
if h > d[-1]:
65+
d.append(h)
66+
else:
67+
idx = bisect_left(d, h)
68+
if idx == len(d):
69+
idx = 0
70+
d[idx] = h
71+
return len(d)
7272
```
7373

7474
### **Java**
@@ -78,24 +78,99 @@ class Solution:
7878
```java
7979
class Solution {
8080
public int maxEnvelopes(int[][] envelopes) {
81-
int n;
82-
if (envelopes == null || (n = envelopes.length) == 0) return 0;
8381
Arrays.sort(envelopes, (a, b) -> {
8482
return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
8583
});
86-
int[] dp = new int[n];
87-
Arrays.fill(dp, 1);
88-
int res = 1;
84+
int n = envelopes.length;
85+
int[] d = new int[n + 1];
86+
d[1] = envelopes[0][1];
87+
int size = 1;
8988
for (int i = 1; i < n; ++i) {
90-
for (int j = 0; j < i; ++j) {
91-
if (envelopes[j][1] < envelopes[i][1]) {
92-
dp[i] = Math.max(dp[i], dp[j] + 1);
89+
int x = envelopes[i][1];
90+
if (x > d[size]) {
91+
d[++size] = x;
92+
} else {
93+
int left = 1, right = size;
94+
while (left < right) {
95+
int mid = (left + right) >> 1;
96+
if (d[mid] >= x) {
97+
right = mid;
98+
} else {
99+
left = mid + 1;
100+
}
93101
}
102+
int p = d[left] >= x ? left : 1;
103+
d[p] = x;
104+
}
105+
}
106+
return size;
107+
}
108+
}
109+
```
110+
111+
### **C++**
112+
113+
```cpp
114+
class Solution {
115+
public:
116+
int maxEnvelopes(vector<vector<int>>& envelopes) {
117+
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
118+
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
119+
});
120+
int n = envelopes.size();
121+
vector<int> d{envelopes[0][1]};
122+
for (int i = 1; i < n; ++i)
123+
{
124+
int x = envelopes[i][1];
125+
if (x > d[d.size() - 1]) d.push_back(x);
126+
else
127+
{
128+
int idx = lower_bound(d.begin(), d.end(), x) - d.begin();
129+
if (idx == d.size()) idx = 0;
130+
d[idx] = x;
94131
}
95-
res = Math.max(res, dp[i]);
96132
}
97-
return res;
133+
return d.size();
98134
}
135+
};
136+
```
137+
138+
### **Go**
139+
140+
```go
141+
func maxEnvelopes(envelopes [][]int) int {
142+
sort.Slice(envelopes, func(i, j int) bool {
143+
if envelopes[i][0] != envelopes[j][0] {
144+
return envelopes[i][0] < envelopes[j][0]
145+
}
146+
return envelopes[j][1] < envelopes[i][1]
147+
})
148+
n := len(envelopes)
149+
d := make([]int, n+1)
150+
d[1] = envelopes[0][1]
151+
size := 1
152+
for _, e := range envelopes[1:] {
153+
x := e[1]
154+
if x > d[size] {
155+
size++
156+
d[size] = x
157+
} else {
158+
left, right := 1, size
159+
for left < right {
160+
mid := (left + right) >> 1
161+
if d[mid] >= x {
162+
right = mid
163+
} else {
164+
left = mid + 1
165+
}
166+
}
167+
if d[left] < x {
168+
left = 1
169+
}
170+
d[left] = x
171+
}
172+
}
173+
return size
99174
}
100175
```
101176

‎solution/0300-0399/0354.Russian Doll Envelopes/README_EN.md

Lines changed: 95 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -46,47 +46,120 @@
4646
```python
4747
class Solution:
4848
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
49-
if not envelopes:
50-
return 0
5149
envelopes.sort(key=lambda x: (x[0], -x[1]))
52-
nums = [x[1] for x in envelopes]
53-
n = len(nums)
54-
dp = [1] * n
55-
res = 1
56-
for i in range(1, n):
57-
for j in range(i):
58-
if nums[j] < nums[i]:
59-
dp[i] = max(dp[i], dp[j] + 1)
60-
res = max(res, dp[i])
61-
return res
50+
d = [envelopes[0][1]]
51+
for _, h in envelopes[1:]:
52+
if h > d[-1]:
53+
d.append(h)
54+
else:
55+
idx = bisect_left(d, h)
56+
if idx == len(d):
57+
idx = 0
58+
d[idx] = h
59+
return len(d)
6260
```
6361

6462
### **Java**
6563

6664
```java
6765
class Solution {
6866
public int maxEnvelopes(int[][] envelopes) {
69-
int n;
70-
if (envelopes == null || (n = envelopes.length) == 0) return 0;
7167
Arrays.sort(envelopes, (a, b) -> {
7268
return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
7369
});
74-
int[] dp = new int[n];
75-
Arrays.fill(dp, 1);
76-
int res = 1;
70+
int n = envelopes.length;
71+
int[] d = new int[n + 1];
72+
d[1] = envelopes[0][1];
73+
int size = 1;
7774
for (int i = 1; i < n; ++i) {
78-
for (int j = 0; j < i; ++j) {
79-
if (envelopes[j][1] < envelopes[i][1]) {
80-
dp[i] = Math.max(dp[i], dp[j] + 1);
75+
int x = envelopes[i][1];
76+
if (x > d[size]) {
77+
d[++size] = x;
78+
} else {
79+
int left = 1, right = size;
80+
while (left < right) {
81+
int mid = (left + right) >> 1;
82+
if (d[mid] >= x) {
83+
right = mid;
84+
} else {
85+
left = mid + 1;
86+
}
8187
}
88+
int p = d[left] >= x ? left : 1;
89+
d[p] = x;
8290
}
83-
res = Math.max(res, dp[i]);
8491
}
85-
return res;
92+
return size;
8693
}
8794
}
8895
```
8996

97+
### **C++**
98+
99+
```cpp
100+
class Solution {
101+
public:
102+
int maxEnvelopes(vector<vector<int>>& envelopes) {
103+
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
104+
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
105+
});
106+
int n = envelopes.size();
107+
vector<int> d{envelopes[0][1]};
108+
for (int i = 1; i < n; ++i)
109+
{
110+
int x = envelopes[i][1];
111+
if (x > d[d.size() - 1]) d.push_back(x);
112+
else
113+
{
114+
int idx = lower_bound(d.begin(), d.end(), x) - d.begin();
115+
if (idx == d.size()) idx = 0;
116+
d[idx] = x;
117+
}
118+
}
119+
return d.size();
120+
}
121+
};
122+
```
123+
124+
### **Go**
125+
126+
```go
127+
func maxEnvelopes(envelopes [][]int) int {
128+
sort.Slice(envelopes, func(i, j int) bool {
129+
if envelopes[i][0] != envelopes[j][0] {
130+
return envelopes[i][0] < envelopes[j][0]
131+
}
132+
return envelopes[j][1] < envelopes[i][1]
133+
})
134+
n := len(envelopes)
135+
d := make([]int, n+1)
136+
d[1] = envelopes[0][1]
137+
size := 1
138+
for _, e := range envelopes[1:] {
139+
x := e[1]
140+
if x > d[size] {
141+
size++
142+
d[size] = x
143+
} else {
144+
left, right := 1, size
145+
for left < right {
146+
mid := (left + right) >> 1
147+
if d[mid] >= x {
148+
right = mid
149+
} else {
150+
left = mid + 1
151+
}
152+
}
153+
if d[left] < x {
154+
left = 1
155+
}
156+
d[left] = x
157+
}
158+
}
159+
return size
160+
}
161+
```
162+
90163
### **...**
91164

92165
```

‎solution/0300-0399/0354.Russian Doll Envelopes/Solution.cpp

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
class Solution {
2+
public:
3+
int maxEnvelopes(vector<vector<int>>& envelopes) {
4+
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
5+
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
6+
});
7+
int n = envelopes.size();
8+
vector<int> d{envelopes[0][1]};
9+
for (int i = 1; i < n; ++i)
10+
{
11+
int x = envelopes[i][1];
12+
if (x > d[d.size() - 1]) d.push_back(x);
13+
else
14+
{
15+
int idx = lower_bound(d.begin(), d.end(), x) - d.begin();
16+
if (idx == d.size()) idx = 0;
17+
d[idx] = x;
18+
}
19+
}
20+
return d.size();
21+
}
22+
};

‎solution/0300-0399/0354.Russian Doll Envelopes/Solution.go

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
func maxEnvelopes(envelopes [][]int) int {
2+
sort.Slice(envelopes, func(i, j int) bool {
3+
if envelopes[i][0] != envelopes[j][0] {
4+
return envelopes[i][0] < envelopes[j][0]
5+
}
6+
return envelopes[j][1] < envelopes[i][1]
7+
})
8+
n := len(envelopes)
9+
d := make([]int, n+1)
10+
d[1] = envelopes[0][1]
11+
size := 1
12+
for _, e := range envelopes[1:] {
13+
x := e[1]
14+
if x > d[size] {
15+
size++
16+
d[size] = x
17+
} else {
18+
left, right := 1, size
19+
for left < right {
20+
mid := (left + right) >> 1
21+
if d[mid] >= x {
22+
right = mid
23+
} else {
24+
left = mid + 1
25+
}
26+
}
27+
if d[left] < x {
28+
left = 1
29+
}
30+
d[left] = x
31+
}
32+
}
33+
return size
34+
}

0 commit comments

Comments
 (0)