Сложность: hard
Вам дан двумерный массив целых чисел 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 {
func lengthOfLIS(_ nums: [Int]) -> Int {
var dp = [Int](repeating: 0, count: nums.count)
var len = 0
for num in nums {
var i = dp.binarySearch(0..<len, num)
if i < 0 { i = -(i + 1) }
dp[i] = num
if i == len { len += 1 }
}
return len
}
func maxEnvelopes(_ envelopes: [[Int]]) -> Int {
let sortedEnvelopes = envelopes.sorted {
if $0[0] == $1[0] { return $0[1] > $1[1] }
return $0[0] < $1[0]
}
let secondDim = sortedEnvelopes.map { $0[1] }
return lengthOfLIS(secondDim)
}
}
extension Array where Element == Int {
func binarySearch(_ range: Range<Int>, _ target: Int) -> Int {
var left = range.lowerBound
var right = range.upperBound
while left < right {
let mid = left + (right - left) / 2
if self[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left < range.upperBound && self[left] == target ? left : -(left + 1)
}
}Ставь 👍 и забирай 📚 Базу знаний