Сложность: 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 {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer[]
*/
function mostCompetitive($nums, $k) {
$queue = [];
$additionalCount = count($nums) - $k;
foreach ($nums as $num) {
while (!empty($queue) && end($queue) > $num && $additionalCount > 0) {
array_pop($queue);
$additionalCount--;
}
$queue[] = $num;
}
return array_slice($queue, 0, $k);
}
}Ставь 👍 и забирай 📚 Базу знаний