力扣3542题：利用单调栈轻松解决元素变0

在算法学习中，数组操作类问题是非常基础但又极具挑战性的题型。今天我们要探讨的力扣3542题就是一个典型的数组操作问题，它要求我们找到将数组中所有元素变为零的最少操作次数。

一、问题重述

给定一个非负整数数组，每次操作可以选择一个子数组，将该子数组中最小的非负整数设为0。我们的目标是计算将整个数组变为0所需的最少操作次数。

示例

输入：[1,2,3,2,1] 输出：3 解释： 第一次操作选择整个数组，最小值1被设为0 → [0,2,3,2,0] 第二次操作选择子数组[2,3,2]，最小值2被设为0 → [0,0,3,0,0] 第三次操作选择子数组[3]，最小值3被设为0 → [0,0,0,0,0]

二、解题思路分析

1.直观理解

最直观的想法是每次操作选择整个数组，这样每次都能消除当前数组中的最小值。但这种策略往往不是最优的，例如对于[1,2,1]这样的数组，只需要2次操作而非3次。

2.关键观察

1. 层级关系：较大的数字需要在其所有较小的数字被消除后才能被消除

2. 单调性：我们可以利用单调递增栈来跟踪需要独立操作的数值

3. 操作次数：每个需要独立操作的数值都会增加总操作次数

3.单调栈的应用

单调栈是解决这类问题的利器：

• 栈中存储的是需要独立操作的数值

• 维护栈的单调递增性质

• 每当遇到一个比栈顶小的数字时，弹出比它大的元素

三、完整代码

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;
    }
};

四、代码执行流程

1. 初始化操作次数res为0和空栈stk

2. 遍历数组中的每个元素num

3. 维护栈的单调性：弹出所有大于num的栈顶元素

4. 如果num不为0且满足独立操作条件，则增加操作次数并将num入栈

5. 返回总操作次数

五、常见错误

1. 忽略0值：忘记处理数组中已经为0的元素

2. 栈操作错误：没有正确维护单调栈的性质

3. 边界条件：空数组或全0数组的处理

4. 操作次数计算：错误地增加操作次数

六、总结

通过这道题，我们理解了单调栈的应用和将问题抽象为栈操作。对于提升算法思维和解决实际问题都有很大帮助。