3948. Lexicographically Maximum MEX Array

You are given an integer array nums.

You want to construct an array result by repeatedly performing the following operation until nums becomes empty:

• Choose an integer k such that 1 <= k <= len(nums).
• Compute the MEX of the first k elements of nums.
• Append this MEX to result.
• Remove the first k elements from nums.

Return the lexicographically maximum array result that can be obtained after performing the operations.

The MEX of an array is the smallest non-negative integer not present in the array.

An array a is lexicographically greater than an array b if in the first position where a and b differ, array a has an element that is greater than the corresponding element in b. If the first min(a.length, b.length) elements do not differ, then the longer array is the lexicographically greater one.

class Solution {
public:
    vector<int> maximumMEX(vector<int>& nums) {
        unordered_map<int,deque<int>> at;
        for(int i = 0; i < nums.size(); i++) at[nums[i]].push_back(i);
        vector<int> res;
        int pos = 0;
        while(at.count(0)) {
            int val = 0, now = pos;
            while(at.count(val)) {
                now = max(now, at[val][0]);
                val++;
            }
            res.push_back(val);
            for(; pos <= now; pos++) {
                at[nums[pos]].pop_front();
                if(at[nums[pos]].size() == 0) at.erase(nums[pos]);
            }
        }
        for(; pos < nums.size(); pos++) res.push_back(0);
        return res;
    }
};