Задача: 354. Russian Doll Envelopes
Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.
Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).
Примечание: Вы не можете поворачивать конверт.
Пример:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
👨💻 Алгоритм:
1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).
2⃣Извлеките вторую размерность (высоты) отсортированного массива.
3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.
😎 Решение:
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for num in nums:
i = bisect_left(dp, num)
if i < len(dp):
dp[i] = num
else:
dp.append(num)
return len(dp)
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
second_dim = [e[1] for e in envelopes]
return self.lengthOfLIS(second_dim)
👉Новости 👉Платформа