数组中大小为 k 的最小词典子序列

Question

给定一个整数数组，找出大小为 k 的最小词法子序列。 EX: Array : [3,1,5,3,5,9,2] k =4 Expected Soultion : 1 3 5 2

Answer 1

这个问题可以通过维护一个双端队列（deque）在 O(n) 中解决。我们从左到右迭代元素，并确保双端队列始终保持到该点的最小词典序列。如果当前元素小于 deque 中的元素并且 deque 中的总元素加上要处理的剩余元素至少为 k，我们应该只弹出元素。

vector<int> smallestLexo(vector<int> s, int k) {
    deque<int> dq;
    for(int i = 0; i < s.size(); i++) {
        while(!dq.empty() && s[i] < dq.back() && (dq.size() + (s.size() - i - 1)) >= k) {
            dq.pop_back();
        }
        dq.push_back(s[i]);
    }
    return vector<int> (dq.begin(), dq.end());
}