Задача: 354. Russian Doll Envelopes
Сложность: 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 {
    function lengthOfLIS($nums) {
        $dp = [];
        foreach ($nums as $num) {
            $i = $this->binarySearch($dp, $num);
            if ($i < 0) $i = -($i + 1);
            $dp[$i] = $num;
        }
        return count($dp);
    }

    function binarySearch($arr, $target) {
        $left = 0;
        $right = count($arr);
        while ($left < $right) {
            $mid = intdiv($left + $right, 2);
            if ($arr[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        return ($left < count($arr) && $arr[$left] == $target) ? $left : -($left + 1);
    }

    function maxEnvelopes($envelopes) {
        usort($envelopes, function($a, $b) {
            return $a[0] == $b[0] ? $b[1] - $a[1] : $a[0] - $b[0];
        });
        $secondDim = array_map(function($envelope) {
            return $envelope[1];
        }, $envelopes);
        return $this->lengthOfLIS($secondDim);
    }
}

Ставь 👍 и забирай 📚 Базу знаний