Сложность: medium
Дан целочисленный массив nums и положительное целое число k. Верните наиболее конкурентоспособную подпоследовательность массива nums размера k.
Подпоследовательность массива — это результирующая последовательность, полученная путем удаления некоторых (возможно, нуля) элементов из массива.
Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5.
Пример:
Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.
👨💻 Алгоритм:
1⃣Создайте двустороннюю очередь (deque), которая будет хранить выбранную подпоследовательность.
2⃣Переберите массив nums, выбирая наиболее конкурентоспособные элементы и добавляя их в очередь. Сравнивайте последний элемент в очереди с текущим элементом, удаляя из очереди более крупные элементы, если можно удалить больше элементов, чем необходимо для достижения размера k.
3⃣В конце получите первые k элементов из очереди и создайте результирующий массив.
😎 Решение:
class Solution {
public int[] mostCompetitive(int[] nums, int k) {
Deque<Integer> queue = new ArrayDeque<Integer>();
int additionalCount = nums.length - k;
for (int i = 0; i < nums.length; i++) {
while (!queue.isEmpty() && queue.peekLast() > nums[i] && additionalCount > 0) {
queue.pollLast();
additionalCount--;
}
queue.addLast(nums[i]);
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = queue.pollFirst();
}
return result;
}
}Ставь 👍 и забирай 📚 Базу знаний