LeetCode 3542题：单调栈优化最小操作次数问题

一、题目解读

LeetCode 3527题要求对给定数组进行操作，通过一系列步骤将其调整为特定状态（或满足特定条件）。题目核心在于通过最小操作次数实现目标，通常涉及数组元素顺序调整或状态转换。理解题目约束条件（如元素限制、操作定义）是解题关键。

二、解题思路

采用“单调栈+贪心策略”求解。核心思想是维护一个单调递增栈，通过入栈/出栈操作确保栈内元素严格递增。每次遍历数组元素时，若当前元素破坏栈单调性，则弹出栈顶元素直至恢复单调；当栈为空或当前元素需新增操作时，计数加一。此策略保证每一步操作均为必要且最优，避免冗余调整。

三、解题步骤

1. 初始化结果res=0，创建单调递增栈stk。

2. 遍历数组nums：

○ 若栈不空且栈顶>当前元素，持续弹出栈顶（消除“逆序”元素）。

○ 若当前元素num≠0且栈空或栈顶<num，执行新增操作（res++）并入栈。

3. 返回最终操作次数res。

步骤关键：通过“逆序弹出”维护单调性，仅当“必要新增”时才计入操作，确保全局最优解。

四、代码与注释

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int res = 0;
        stack<int> stk;

        for (int num : nums) {
            // 维护单调递增栈
            while (!stk.empty() && stk.top() > num) {
                stk.pop();
            }

            // 只有当当前数字不为0且栈为空或栈顶小于当前数字时才需要增加操作次数
            if (num != 0 && (stk.empty() || stk.top() < num)) {
                res++;
                stk.push(num);
            }
        }

        return res;
    }
};

代码注释解析：

● 循环逻辑紧扣“单调性维护”与“新增操作判定”，通过条件分支精准捕捉必要步骤。

● 栈操作与计数逻辑紧密耦合，避免重复或无效调整。

五、总结

本题通过单调栈将复杂操作序列转化为局部最优决策，核心在于识别“必须新增”与“可消除”的两种情况。算法时间复杂度O(n)（单次遍历+栈操作），空间复杂度O(n)（栈最大容量）。掌握此类“栈+贪心”模型可高效解决类似数组调整问题，提升算法设计能力。