problem:221021天池-03. 整理书架

思路：可以先去刷母题，母题的变形题。链接，比母题多了limit的限制。

Accode:

class Solution {
public:
    vector<int> arrangeBookshelf(vector<int>& order, int limit) {
        unordered_map<int,int> cnts;
        unordered_map<int,int> ans_cnt;
        vector<int> ans;
        for(auto item:order){
            cnts[item]++;
        }
        for(int i=0;i<order.size();i++){
            //cnts[order[i]]--;
            if(ans_cnt[order[i]]>=limit){
                cnts[order[i]]--;
                continue;
            }
            while(ans.size() && ans.back()>order[i]){
                if(cnts[ans.back()]-1+ans_cnt[ans.back()]>=limit){
                    ans_cnt[ans.back()]--;
                    ans.pop_back();
                }
                else break;
            }
            cnts[order[i]]--;
            ans.push_back(order[i]);
            ans_cnt[order[i]]++;
        }
        return ans;
    }
};

时间复杂度:$o(n)$