1673. Find the Most Competitive Subsequence

leetcode medium

#array#csharp#graph#leetcode#medium#queue#search

Task

Дан целочисленный массив 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.

C# solution

matched/original

public class Solution {
    public int[] MostCompetitive(int[] nums, int k) {
        var queue = new LinkedList<int>();
        int additionalCount = nums.Length - k;
        
        foreach (int num in nums) {
            while (queue.Count > 0 && queue.Last.Value > num && additionalCount > 0) {
                queue.RemoveLast();
                additionalCount--;
            }
            queue.AddLast(num);
        }
        
        return queue.Take(k).ToArray();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& MostCompetitive(vector<int>& nums, int k) {
        var queue = new LinkedList<int>();
        int additionalCount = nums.size() - k;
        
        foreach (int num in nums) {
            while (queue.size() > 0 && queue.Last.Value > num && additionalCount > 0) {
                queue.RemoveLast();
                additionalCount--;
            }
            queue.AddLast(num);
        }
        
        return queue.Take(k).ToArray();
    }
}

Java solution

matched/original

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;
    }
}

JavaScript solution

matched/original

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);
};

Go solution

matched/original

func mostCompetitive(nums []int, k int) []int {
    queue := make([]int, 0)
    additionalCount := len(nums) - k
    
    for _, num := range nums {
        for len(queue) > 0 && queue[len(queue)-1] > num && additionalCount > 0 {
            queue = queue[:len(queue)-1]
            additionalCount--
        }
        queue = append(queue, num)
    }
    
    return queue[:k]
}

Explanation

Algorithm

Создайте двустороннюю очередь (deque), которая будет хранить выбранную подпоследовательность.

Переберите массив nums, выбирая наиболее конкурентоспособные элементы и добавляя их в очередь. Сравнивайте последний элемент в очереди с текущим элементом, удаляя из очереди более крупные элементы, если можно удалить больше элементов, чем необходимо для достижения размера k.

В конце получите первые k элементов из очереди и создайте результирующий массив.

😎