Сложность: 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 элементов из очереди и создайте результирующий массив.
😎 Решение:
var mostCompetitive = function(nums, k) {
let queue = [];
let additionalCount = nums.length - k;
for (let num of nums) {
while (queue.length > 0 && queue[queue.length - 1] > num && additionalCount > 0) {
queue.pop();
additionalCount--;
}
queue.push(num);
}
return queue.slice(0, k);
};Ставь 👍 и забирай 📚 Базу знаний