数组删除比左侧小元素的操作次数求解及代码优化

你当前需要实现的是重复删除数组中所有比左侧相邻元素小的元素，统计总操作轮次，现有暴力模拟的实现存在性能瓶颈。

你现有的实现是逐轮模拟删除过程，最坏时间复杂度为O(n²)：比如输入严格递减的数组时，需要执行n-1轮操作，每轮都要遍历当前剩余的所有元素，当数组长度较大时运行效率会非常低。

我们可以通过一次遍历+单调栈的方式直接计算出每个元素被删除的轮次，所有元素删除轮次的最大值就是我们要求的总操作次数：

• 栈中存储(元素值, 该元素被删除的轮次)对，维护栈内元素值单调不下降
• 对于每个新元素，弹出栈中所有比当前元素小的元素，记录弹出的元素中最大的删除轮次max_del
• 如果弹出后栈不为空，说明当前元素会被栈顶的更大元素删除：
  • 如果弹出过元素，当前元素的删除轮次是max_del + 1
  • 如果没弹出过元素，当前元素的删除轮次是1
• 如果弹出后栈为空，说明当前元素是左侧最大的，不会被删除，删除轮次记为0
• 全局维护所有删除轮次的最大值，就是最终答案

#include <stack>
#include <algorithm>
using namespace std;

int numberOfTimes(int array[], int n) {
    if (n <= 1) return 0;
    stack<pair<int, int>> st;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int cur_del = 0;
        // 弹出栈中比当前元素小的元素
        while (!st.empty() && st.top().first < array[i]) {
            cur_del = max(cur_del, st.top().second);
            st.pop();
        }
        // 栈不为空，当前元素会被删除
        if (!st.empty()) {
            cur_del += 1;
            res = max(res, cur_del);
        }
        // 入栈
        st.push({array[i], cur_del});
    }
    return res;
}

• 时间复杂度：O(n)，每个元素只会入栈和出栈各一次
• 空间复杂度：O(n)，最坏情况栈中需要存储所有元素（比如严格递增的数组）

输入你给出的测试用例[10, 9, 7, 8, 6, 5, 3, 4, 2, 1]，上述代码返回结果为2，和预期一致。

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