3542. Minimum Operations to Convert All Elements to Zero

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

本题给我们一个数字数组 nums，要求我们经过一系列操作之后，把 nums 数组全部元素变为 0

题目要求我们求最少要多少次操作

每次操作我们都需要选择任意子数组，然后将子数组中最小的元素置为 0

解题思路

根据题目所述，我们的最优解法就是：

1. 把整个数组当成子数组，然后把最小的元素全部置为 0
2. 把剩下的数组从 0 的位置分为多个子数组，然后分别执行第一步
3. 如果整个数组都为 0 了就终止操作

根据上述思路，我们可以再进一步思考一下，该如何简化

我们使用 [1, 2, 3, 2, 3] 这个例子来解释：

1. 首先考虑单调递增的情况，也就是开头的 [1, 2, 3] 这种情况我们不难看出需要三次的操作
2. 紧接着我们多考虑一位：[1, 2, 3, 2] 这种情况依然需要三次操作
3. 下一步：[1, 2, 3, 2, 3] 这次需要四次操作

看出区别了吗？只要是后面一位比前一位大，我们都是需要进行额外的操作的

那么问题就变成了，我们要如何记录上一位的数字大小呢？

我们可以使用一个栈 stack ，以下是步骤说明：

1. 由于前三位是递增，我们将其依序入栈，此时 stack = [1, 2, 3]，需要的操作为 3 次
2. 第四位出现了 2，比当前的栈顶 3 小，所以我们需要把当前栈顶依序出栈直到当前栈顶小于等于 2，操作次数不变
3. 第五位出现了 3，此时栈顶为 2，我们需要把 3 入栈，操作数也需要加一，此时为 4
4. 数组遍历完毕，返回操作数 4

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function(nums) {
    const stack = []
    let res = 0

    for(const num of nums) {
        while(stack.length && stack[stack.length - 1] > num) {
            stack.pop()
        }
        // if the num is already 0, then do nothing
        if(num === 0) {
            continue
        }
        // if current number is larger than stack top, we must apply 1 extra op to make it 0
        if(stack.length === 0 || stack[stack.length - 1] < num) {
            res++
            stack.push(num)
        }
    }

    return res
};