如何优化统计数组多次删除左大右小元素所需轮次的算法

原代码的时间复杂度问题 #

你当前的暴力模拟实现最坏时间复杂度为O(n²)：比如输入严格降序数组时，每轮只能删除1个元素，总共有n轮遍历，当n规模较大时性能会很差。

O(n)时间复杂度的单调栈解法 #

我们不需要逐轮模拟删除过程，只需要统计每个元素被删除的轮次，所有元素删除轮次的最大值就是要返回的操作轮次。
核心逻辑：

• 每个元素如果会被删除，必然是被它左侧第一个比它大的元素删除
• 元素的删除轮次 = 它和左侧第一个更大元素之间所有元素的删除轮次的最大值 + 1
• 左侧没有更大元素的元素不会被删除，删除轮次为0

实现代码 #

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

int Mafia(int n, vector<int> input_array) {
    // 栈中存储 pair<元素值, 该元素的删除轮次>
    stack<pair<int, int>> st;
    int max_round = 0;
    for (int num : input_array) {
        int cur_round = 0;
        // 弹出所有比当前元素小的栈中元素，统计中间最大删除轮次
        while (!st.empty() && st.top().first < num) {
            cur_round = max(cur_round, st.top().second);
            st.pop();
        }
        // 栈不为空说明当前元素会被左侧更大元素删除
        if (!st.empty()) {
            cur_round++;
            max_round = max(max_round, cur_round);
        }
        st.push({num, cur_round});
    }
    return max_round;
}

验证效果 #

• 示例1输入[10, 9, 7, 8, 6, 5, 3, 4, 2, 1]，计算得到最大轮次为2，和预期结果一致
• 示例2输入[1,2,3,4]，所有元素左侧都没有更大元素，最大轮次为0，和预期结果一致

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