Is there a way to further optimize this code?

Question

2289, LeetCode. Steps To make array non-decreasing You are given a 0-indexed integer array nums. In one step, remove all elements nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length.

Return the number of steps performed until nums becomes a non-decreasing array.
Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
Output: 3
Explanation: The following are the steps performed:

• Step 1: [5,3,4,4,7,3,6,11,8,5,11] becomes [5,4,4,7,6,11,11]
• Step 2: [5,4,4,7,6,11,11] becomes [5,4,7,11,11]
• Step 3: [5,4,7,11,11] becomes [5,7,11,11]
  [5,7,11,11] is a non-decreasing array. Therefore, we return 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;
    }
};

I am currently passing 84/87 tests on leetcode, with the remaining ones exceeding the time limit.

Answer 1

There is a solution with linear time and space complexity. Let us consider the number of steps to remove the element at any index i. There must exist an index j such that j < i and nums[j] > nums[i]. More specifically, the largest j (i.e. the closest larger element on the left) that satisfies this condition will cause the deletion of the element at index i.

All the elements between indexes j and i must be removed before i becomes adjacent to j and can be removed. Thus, the number of steps to remove i is one more than the maximum number of steps to remove any element between j and i.

We can maintain a monotonic stack of indexes (with elements in increasing order from top to bottom) for the full solution.

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;
}