LeetCode 2289题代码优化求助：现有解法超时未通过全部测试

问题背景 #

LeetCode 2289题：使数组非递减的步骤数。给定0索引整数数组nums，每一步移除所有满足nums[i-1] > nums[i]（0 < i < nums.length）的元素nums[i]，返回数组变为非递减数组所需的步数。

示例输入：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]，此时数组非递减，返回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的测试用例，剩余测试用例因超出时间限制未通过，需要优化。

优化方案 #

原代码问题分析 #

原代码的核心问题在于模拟每一步删除过程的时间成本太高：

• 每次循环都要遍历整个数组标记待删除元素，时间复杂度O(n)
• 数组erase操作是O(n)复杂度，且每次可能删除多个元素
• 最坏情况下时间复杂度达到O(n²)，面对大规模测试用例必然超时

优化思路：单调栈计算删除步数 #

不用模拟删除过程，转而计算每个元素被删除需要的步数，最终取所有元素的最大步数即可。利用单调栈可以在O(n)时间内完成计算：

• 栈中存储(元素值, 该元素被删除的步数)，维护栈的单调递减性（栈顶元素最小）
• 遍历数组时，对于当前元素，弹出栈中所有小于等于它的元素（这些元素会先被删除），记录这些元素的最大步数
• 如果栈不为空，当前元素的删除步数为最大步数 + 1（因为要等前面的元素处理完才会轮到它），同时更新全局最大步数；否则当前元素不会被删除，步数为0

优化后的代码 #

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        stack<pair<int, int>> st;
        int maxSteps = 0;
        for (int num : nums) {
            int currentMax = 0;
            // 弹出所有比当前元素小或相等的元素，记录它们的最大删除步数
            while (!st.empty() && st.top().first <= num) {
                currentMax = max(currentMax, st.top().second);
                st.pop();
            }
            // 栈不为空说明当前元素会被前面的元素触发删除
            if (!st.empty()) {
                currentMax += 1;
                maxSteps = max(maxSteps, currentMax);
            } else {
                currentMax = 0;
            }
            st.push({num, currentMax});
        }
        return maxSteps;
    }
};

代码说明 #

以示例数组为例：

• 元素4（原数组索引2）的删除步数是2：它在第一步不会被删（因为前面的3被删了），第二步才会被5触发删除，所以步数是2
• 元素4（原数组索引3）的删除步数是3：第一步、第二步都没被删，第三步才被5触发删除，所以步数是3
• 全局最大步数是3，正好匹配示例输出

这个解法的时间复杂度是O(n)，每个元素最多进栈出栈一次，空间复杂度O(n)，可以轻松通过所有测试用例。

内容的提问来源于stack exchange，提问作者Diplo2