有没有办法进一步优化这段代码？

Question

2289，LeetCode。使数组不减的步骤 给定一个 0 索引的整数数组 nums。一步删除所有元素 nums[i]，其中 nums[i - 1] > nums[i] 为所有 0 < i < nums.length.

返回 nums 成为非递减数组之前执行的步骤数。 输入：nums = [5,3,4,4,7,3,6,11,8,5,11] 输出：3 说明：以下是执行的步骤：

• 第 1 步：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11 ]
• 第 2 步：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]
• 第 3 步：[5,4,7,11,11] 变为 [5,7,11,11] [5,7,11,11] 是一个非递减数组。因此，我们返回 3。

class Solution {
public:
    // 84/87
    int totalSteps(vector<int>& nums) {
        int i;
        int steps = 0;
        
        
        set <int> indexes;

        while(1)
        {
            // marking indexes where found breaking of order
            for(i=1; i<nums.size(); i++) if(nums[i-1]>nums[i]) indexes.insert(i);
            // deleting them
            if(indexes.size()==0) break; // vector is only increasing
            for (auto it = indexes.rbegin(); it != indexes.rend(); ++it) nums.erase(nums.begin() + *it);
            
            indexes.clear();
            ++steps;
        }

    return steps;
    }
};

我目前在leetcode上通过了84/87次测试，剩下的都超过了时间限制。

Answer 1

存在一个具有线性时间和空间复杂度的解。让我们考虑删除任意索引

i

处的元素的步骤数。必须存在一个索引

j

，使得

j < i

和

nums[j] > nums[i]

。更具体地说，满足此条件的最大

j

（即左侧最近的较大元素）将导致索引

i

处的元素被删除。

索引

j

和

i

之间的所有元素必须在

i

与

j

相邻并且可以被删除之前删除。因此，删除

i

的步骤数比删除

j

和

i

之间的任何元素的最大步骤数多 1。

我们可以维护一个单调的索引堆栈（元素从上到下按递增顺序）以获得完整的解决方案。

int totalSteps(vector<int>& nums) {
    stack<int> s;
    int ans = 0;
    vector<int> steps(nums.size());
    for (int i = 0; i < nums.size(); i++) {
        int curr = 1;
        while (!s.empty() && nums[s.top()] <= nums[i]) 
            curr = max(curr, 1 + steps[s.top()]), s.pop();
        if (!s.empty()) ans = max(ans, steps[i] = curr);
        s.push(i);
    }
    return ans;
}