leetcode 2289. 使数组按非递减顺序排列 未解决

leetcode 2289. 使数组按非递减顺序排列

这道题远没有想象中的简单，如果用暴力常规方法，数据量大的情况下会超时

暴力解1：

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int size = nums.size();
        int res = 0;
        int former = 0,now = 1;
        vector<int> flag;
        while(1){
            former = 0;now = 1;//每一次循环nums[0]一定不为0
            while(now < size){
                if(nums[now] == 0) {
                    now++;continue;
                }
                if(nums[former] > nums[now] && nums[now] != 0){
                    flag.emplace_back(now);
                    former = now;
                    now++; 
                    continue;
                }
                former = now;now++;
            }
            if(flag.size() == 0)  break;
            for(int i = 0;i < flag.size();i++)  nums[flag[i]] = 0;
            flag.clear();
            res++;
        } 
        return res;    
    }
};

暴力解2：

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int res = 0;
        vector<int> flag;
        while(1){
            int size = nums.size();
            for(int i = 1; i < size;i++){
                if(nums[i-1] > nums[i])  flag.emplace_back(i);
            }
            if(flag.size() == 0)  break;
            for(int i = 0;i < flag.size();i++){
                nums.erase(nums.begin()+flag[i]-i);
            }
            flag.clear();
            res++;
        } 
        return res;    
    }
};