Задача
Дан двумерный массив envelopes, где envelopes[i] = [wᵢ, hᵢ] — ширина и высота i-го конверта.
Один конверт может быть вложен в другой, если его ширина и высота строго меньше ширины и высоты другого конверта.
Требуется найти максимальное число конвертов, которые можно вложить друг в друга.
Например,
envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3.
Можно вложить максимум 3 конверта друг в друга: [2,3] => [5,4] => [6,7]
Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
По условию, конверты, одинаковые хотя бы по одному измерению, нельзя вкладывать друг в друга.
Ссылка на leetcode: https://leetcode.com/problems/russian-doll-envelopes/description/
Решение
Когда в задаче вы слышите: "найти максимальное", то большая вероятность того, что задача на динамическое программирование.
Кроме того, сразу ничего, кроме перебора, на ум не приходит: перебрать все возможные комбинации конвертов и найти вариант, при котором число вложенных конвертов будет максимальным. Динамическое программирование, по сути, представляет собой умны перебор. Попробуем решить эту задачу с его помощью.
Решение при помощи Динамического Программирования
Вообще, если вы уже решали другую задачу: Longest Increasing Subsequence, то можно заметить, что это похожая задача. Просто двумерная. Решение этой задачи при помощи динамического программирования есть у меня на youtube-канале: Longest Increasing Subsequence
Давайте применим подход bottom-up. Для этого разобьём задачу на подзадачи и установим связь между решениями подзадач и решением общей задачи.
Подзадача в нашем случае — это значение dp[i] - длина максимальной цепочки вложенных друг в друга конвертов, оканчивающейся на конверте i.
Следует также отметить отличие этой задачи от задачи Longest Increasing Subsequence: там относительный порядок элементов в подпоследовательности не может быть произвольным — он должен совпадать с их порядком в исходной последовательности. В нашей же задаче порядок в исходном массиве может быть произвольным, и сохранять его не нужно; важно лишь, чтобы выполнялось условие вложения одного конверта в другой. Поэтому, чтобы при вычислении dp[i] не ходить по всему массиву конвертов, мы можем отсортировать массив конвертов по его размерам в порядке возрастания, тогда нам достаточно будет проверять все конверты слева(меньшие) от текущего.
Сортировку сделаем по одному из имерений (например, ширине). Более того, если ширина конвертов одинаковая, отсортируем из по возрастанию второго измерения - высоты:
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return Integer.compare(a[1], b[1]);
}
return Integer.compare(a[0], b[0]);
});
Теперь осталось определить связь подзадач и общей задачей. Тут все также как и в Longest Increasing Subsequence. Для вычисления dp[i] нам нужно пройти по всем dp[j] слева от нашего конверта (меньшие), проверить, что они влезают в наш i-конверт. Если влезают, то если dp[j] + 1 > dp[i] обновить dp[i] = dp[j] + 1. Т.е. продолжить последовательность от j конверта и вложить эту матрешку в наш i-конверт.
В коде это будет выглядеть так:
for (int j = 0; j < i; j++) {
if (влезает ли j конверт в i конверт) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
Тогда ответом на задачу будет наибольший dp[i].
В коде все вместе это выглядит так:
public int maxEnvelopes(int[][] envelopes) {
//Сортируем по размерам
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return Integer.compare(a[1], b[1]);
}
return Integer.compare(a[0], b[0]);
});
int[] dp = new int[envelopes.length];
//Инициализиуем единичками
//потому что каждый конверт сам по себе — цепочка длины 1.
Arrays.fill(dp, 1);
int result = 1;
for (int i = 0; i < envelopes.length; i++) {
for (int j = 0; j < i; j++) {
//Влезает ли j конверт в i конверт
if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
//Вычисляем dp[i]
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
//находим цепочку максимальной длины
result = Math.max(result, dp[i]);
}
return result;
}
Time Complexity = O(n*log(n)) + O(n^2) = O(n^2). O(n*log(n)) - берется из сортировки.
Space Complexity = O(n) - на массив dp + O(log(n)) или O(n) - на сортировку = O(n).
Можно ли улучшить это решение? Да, при помощи бинарного поиска.
Решение при помощи Бинарного поиска
Это решение не очевидное и его я не разбирал для Longest Increasing Subsequence. Но ее также можно решить при помощи бинарного поиска.
Для начала, как и в предыдущем варианте решения, отсортируем конверты по одному из измерений, например по ширине. Затем с помощью бинарного поиска будем искать Longest Increasing Subsequence по высотам уже отсортированных конвертов.
Здесь важно учесть один частный случай: когда ширина совпадает. Если при равной ширине дополнительно отсортировать конверты по высоте по возрастанию, бинарный поиск, не учитывая ширину, может решить, что при большей высоте один конверт помещается в другой, хотя это не так.
Например, для набора [(3, 3), (3, 4)] ширина одинакова, и при сортировке по высоте по возрастанию кажется, что 3 < 4, и наш бинарный поиск будет считать, что конверты можно вложить друг в друга. Чтобы этого избежать, отсортируем немного иначе: по ширине — по возрастанию, а при равной ширине — по убыванию высоты:
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return Integer.compare(b[1], a[1]);
} else {
return Integer.compare(a[0], b[0]);
}
});
Теперь для отсотрированного массива применим бинарный поиск по высотам.
Для этого введем такое неочевидное состояние: tails[i] - минимальная высота конверта, на который заканчивается цепочка вложенных конвертов с длинной i + 1. Отличие от предыдущего варианта решения, где у нас в dp[i] мы хранили максимальную длину цепочки, которая заканчивается на i-конверте. Тут мы храним не длину, а минимально возможное значение последнего элемента. В качестве значений у нас будут высоты конвертов.
Далее алгоритм следующий. Инициализирум текущую найденную максимальную длинну цепочки вложенных конвертов 0:
int size = 0
Идем циклом по отсортированному массиву конвертов слева направо. На каждом шаге цикла (для каждого конверта), делаем бинарный поиск по массиву tails в пределах: [0..size), для поиска минимального индекса left, такого, что dp[left] >= h.h - высота текущего конверта.
Если такого элемента нет, т.е. высота текущего конверта больше всех текущих хвостов цепочек, то мы можем создать новую более длинную цепочку с нашим текущим конвертом в конце этой цепочки. Для этого увеличим size на единицу:
//вывалились за пределы, такого элемента нет
//наш конверт больше остальных, поэтому есть цепочка на единицу больше с //нашим конвертом
tails[size] = h
if (left == size) {
size++;
}
Если мы нашли такой элемент, то это значит, что на текущем месте tails[left]>=h и нам нужно обновить это значение, чтобы сохранялось свойство, что в tails[i] мы храним наименьшие конверты, на которые заканчивается цепочка длины i+1.
Все вместе в коде это выглядит так:
public int maxEnvelopes(int[][] envelopes) {
//Сортируем по ширине конвертов
//Если ширина одинаковая - по высоте в порядке убывания
//Иначе подход с бинарным поиском будет считать что если высота больше, то можно конверты вложить, т.к. он не смотрит на ширину
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return Integer.compare(b[1], a[1]);
} else {
return Integer.compare(a[0], b[0]);
}
});
//tails[i] - минимальная высота конверта, на который заканчивается цепочка вложенных конвертов с длинной i + 1
int[] tails = new int[envelopes.length];
int size = 0;
for (int i = 0; i < envelopes.length; i++) {
int h = envelopes[i][1];
int left = 0, right = size;
while (left < right) {
int mid = (left + right) >>> 1;
if (tails[mid] < h) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = h;
if (left == size) {
size++;
}
}
return size;
}
Такое решение работает на O(n*log(n)) по времени и O(n) по памяти.
Top comments (0)