Сложность: 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:
vector<int> mostCompetitive(vector<int>& nums, int k) {
deque<int> queue;
int additionalCount = nums.size() - k;
for (int num : nums) {
while (!queue.empty() && queue.back() > num && additionalCount > 0) {
queue.pop_back();
additionalCount--;
}
queue.push_back(num);
}
return vector<int>(queue.begin(), queue.begin() + k);
}
};Ставь 👍 и забирай 📚 Базу знаний