Question

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Example 1:

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. Example 2:

Input: nums = [2,4,3,3,5,4,9,6], k = 4 Output: [2,3,3,4]

Constraints:

1 <= nums.length <= 105 0 <= nums[i] <= 109 1 <= k <= nums.length

Algorithm-1

(单调栈) O(n)

首先将题目转化成更直观的问题：寻找长度为k的字典序最小的子序列。字典序最小意味着越小的数字应该排在高位，对于当前数字nums[i]，假设现在已经找到了一个子序列长度为k，现在我们想让nums[i]排在这个子序列的第pos个位置，那么意味着子序列里从pos + 1到k - 1的数字应该被排除掉，这也就意味着在原数组里位于nums[i]之前位置的数字被排除掉并且不会被使用，所以想到采用单调栈求解。

但是注意，单调栈里只是近似从栈底到栈顶单增，因为考虑如果对于nums[i]及其后面的数字，和之前已经选出来的数字恰好为k个，此时则不一定是单增。那么判别的一种办法就是用dropNum记录有多少个数字被丢弃掉了，如果dropNum到了n - k，那么从当前数字开始及以后的都直接入栈即可。如果dropNum还未到n - k，则延续单调栈的做法。

于是问题集中在如何处理dropNum，首先当延续单调栈的做法时候，从栈内弹出的数字肯定是要被丢弃的，另外就是栈内的元素已经满掉，并且当前数字不满足进栈条件，也会被丢弃。

时间复杂度O(n) ，空间复杂度O(n) 。

Code-1

C++

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        if (n == k) return nums;

        int dropNum = 0;
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            if ((int)s.size() >= k && nums[i] >= s.top()) {
                ++dropNum;
                continue;
            }

            if (dropNum >= n - k) s.emplace(nums[i]);
            else {
                if (s.empty()) s.emplace(nums[i]);
                else {
                    while (!s.empty() && dropNum < n - k && nums[i] < s.top()) {
                        s.pop();
                        ++dropNum;
                    }
                    s.emplace(nums[i]);
                }
            }
        }

        vector<int> res(k);
        int pos = k - 1;
        while (!s.empty()) {
            res[pos--] = s.top(); s.pop();
        }

        return res;
    }
};

Algorithm-2

给定一个数组A，求其字典序最小的长k的子序列。思路是单调栈。求长k的子序列相当于在A里删掉lA−k个数字。我们用一个变量r标记还可以删多少个数字，一开始赋值为lA−k。接着开一个从栈底到栈顶严格单调上升的栈，如果栈非空并且栈顶大于新来的数，并且还能删数字（指r > 0成立），则出栈，并将r减1，直到栈空或者栈顶小于等于新来的数或者r = 0（这时没法删了），接着将新来的数入栈（如果栈满，说明新来的数无法入栈，则多删一个数，将r减去1）。最后栈底到栈顶的数组即为所求。算法正确性证明，只需要注意每次可以删的时候（这里的删主要指的是pop栈顶），删总是比不删好。代码如下：

Code-2

C++

public class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int[] res = new int[k];
        int idx = 0, rem = nums.length - k;
        for (int i = 0; i < nums.length; i++) {
        	// 如果栈非空并且栈顶大于新来的数，并且还能删数字，则出栈
            while (idx > 0 && res[idx - 1] > nums[i] && rem > 0) {
                idx--;
                rem--;
            }
            
            if (idx < res.length ) {
                res[idx++] = nums[i];
            } else {
                rem--;
            }
        }
        
        return res;
    }
}