题目

给你一个大小为 n 的非负整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得所有元素都变为 0。

在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。

返回使整个数组变为 0 所需的最少操作次数。

一个 子数组 是数组中的一段连续元素。

示例 1：

输入: nums = [0,2]

输出: 1

解释:

选择子数组 [1,1]（即 [2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为 [0,0]。
因此，所需的最少操作次数为 1。

示例 2：

输入: nums = [3,1,2,1]

输出: 3

解释:

选择子数组 [1,3]（即 [1,2,1]），最小非负整数是 1。将所有 1 设为 0，结果为 [3,0,2,0]。
选择子数组 [2,2]（即 [2]），将 2 设为 0，结果为 [3,0,0,0]。
选择子数组 [0,0]（即 [3]），将 3 设为 0，结果为 [0,0,0,0]。
因此，最少操作次数为 3。

示例 3：

输入: nums = [1,2,1,2,1,2]

输出: 4

解释:

选择子数组 [0,5]（即 [1,2,1,2,1,2]），最小非负整数是 1。将所有 1 设为 0，结果为 [0,2,0,2,0,2]。
选择子数组 [1,1]（即 [2]），将 2 设为 0，结果为 [0,0,0,2,0,2]。
选择子数组 [3,3]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,2]。
选择子数组 [5,5]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,0]。
因此，最少操作次数为 4。

提示:

1 <= n == nums.length <= 10^5
0 <= nums[i] <= 10^5

解题思路

一次操作：在某个子数组里，把“最小值等于 m 的那些位置”同时置 0。关键观察：如果我们把数组看成“高度柱状图”，当你选择一段区间时，能一起被清零的，正好是该区间里“等于区间最小高度 h”的所有柱子。要让更多位置一起被清零，区间必须不跨过低于 h 的元素。于是：

对某个正高度 h，只要在被 < h 的元素隔开的每一段连续区域里，所有“恰好等于 h”的位置，都可以通过一次操作清零（取这段区域为子数组即可）。
因而，最少操作数 = 你在从左到右扫描过程中，每次新出现一个“新的正高度层级”（且这个层级之前被更小高度截断过），就需要 +1 次操作。

这正是经典的 Stone Wall（石墙） 计数：从左到右维护一个非降的高度栈，

当当前高度 x 小于栈顶时，说明墙面下降，弹栈直到栈顶 ≤ x；
若此时 x > 0 且（栈空或栈顶 < x），说明出现了一个新的正高度层级，压栈并把答案 +1；
若 x == 栈顶，说明这一层级在延续，不需要新增操作。

这样，每次压入一个正的“新高度”就是必须的一次操作；而所有能被合并在一次操作内的相同高度，会通过“相等不压栈”自然合并；被更小高度切断的同值高度，会在弹栈后再次压入，产生新的必要操作——这与题目中“被 < h 的元素割裂后无法放在同一子数组”严格一致。时间复杂度 O(n)，空间 O(n)。

具体代码

func minOperations(nums []int) int {

    // 栈模拟
    stack := make([]int, 0)
    ans := 0

    for _, num := range nums {

        // 当前元素小于栈顶元素需要出栈到小于等于栈顶的元素或栈空
        for len(stack) != 0 && stack[len(stack) - 1] > num {
            stack = stack[:len(stack) - 1]
        }

        // 0参与比较，当0不参与入栈
        if num == 0 {
            continue
        }

        // 当前元素大于栈顶元素或栈空需要进栈，并且记录一次操作
        if len(stack) == 0 || num > stack[len(stack) - 1] {
            stack = append(stack, num)
            ans++
        }  
    }

    return ans
}

3542. 将所有元素变为 0 的最少操作次数

beautifulremi

题目

解题思路

具体代码