Сложность: 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 {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, len, num);
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == len) {
len++;
}
}
return len;
}
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] arr1, int[] arr2) {
if (arr1[0] == arr2[0]) {
return arr2[1] - arr1[1];
} else {
return arr1[0] - arr2[0];
}
}
});
int[] secondDim = new int[envelopes.length];
for (int i = 0; i < envelopes.length; ++i) secondDim[i] = envelopes[i][1];
return lengthOfLIS(secondDim);
}
}Ставь 👍 и забирай 📚 Базу знаний