如何用单调栈正确求解LeetCode使数组非递减的步数问题

原有实现的问题 #

你之前单独计算每个元素的下一个更大元素（NGE）、上一个更大元素（PGE），再取两个区间长度最小值的思路存在本质错误：

• 题目中的删除操作是每轮同步移除所有满足条件的元素，不是一次性删除两个更大元素之间的所有值，不能直接用区间长度换算删除步数。
• 元素被删除的轮次，取决于它和左侧第一个更大元素之间所有更小元素被删除的轮次，和右侧更大元素的位置没有直接关系。
  比如测试用例[7,3,6]，按原有逻辑计算得到的结果是1，但实际删除流程为：第1轮删除3，数组变为[7,6]；第2轮删除6，总共需要2步，原有逻辑无法得到正确结果。

正确单调栈思路 #

采用单调递减栈求解，栈中存储二元组：(元素值, 当前元素被删除需要的步数)，不会被删除的元素步数记为0，核心逻辑如下：

• 从左到右遍历数组每个元素，初始化当前元素的删除步数为0
• 维护栈的单调递减性质：只要栈不为空且栈顶元素值小于等于当前元素，就弹出栈顶，同时将当前元素的删除步数更新为「当前记录步数」和「弹出元素的删除步数」的最大值——因为当前元素必须等挡在它和左侧更大元素之间的所有元素全部删除后，才会在下一轮被左侧更大元素触发删除
• 弹出操作结束后，如果栈不为空，说明当前元素左侧存在比它大的元素，最终会被删除，当前步数加1；如果栈为空，说明当前元素左侧没有更大值，永远不会被删除，步数保持0
• 将当前元素和对应步数压入栈，全局维护所有元素删除步数的最大值，就是题目要求的总步数

正确C++实现代码 #

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        stack<pair<int, int>> stk;
        int ans = 0;
        for (int num : nums) {
            int cur_step = 0;
            // 维护单调递减栈，弹出所有不大于当前值的栈顶元素
            while (!stk.empty() && stk.top().first <= num) {
                cur_step = max(cur_step, stk.top().second);
                stk.pop();
            }
            // 栈非空说明当前元素会被左侧更大值删除，步数+1
            cur_step = stk.empty() ? 0 : cur_step + 1;
            ans = max(ans, cur_step);
            stk.push({num, cur_step});
        }
        return ans;
    }
};

示例验证 #

针对示例输入nums = [5,3,4,4,7,3,6,11,8,5,11]，遍历过程中记录到的最大删除步数为3，和示例输出一致，对应3轮删除后数组变为非递减状态。

内容的提问来源于stack exchange，提问作者J. Doe