[LeetCode] 3542. Minimum Operations to Convert All Elements to Zero

https://leetcode.com/problems/minimum-operations-to-convert-all-elements-to-zero/description/?envType=daily-question&envId=2025-11-10

LeetCode - Minimum Operations to Convert All Elements to Zero

문제 유형: 모노토닉 스택(단조 증가 스택)

문제 난이도: Medium

 

문제

You are given an array nums of size n, consisting of non-negative integers. Your task is to apply some (possibly zero) operations on the array so that all elements become 0.

In one operation, you can select a subarray [i, j] (where 0 <= i <= j < n) and set all occurrences of the minimum non-negative integer in that subarray to 0.

Return the minimum number of operations required to make all elements in the array 0.

 

음이 아닌 n개의 정수가 들어있는 배열 nums가 주어진다.

당신은 0회 이상의 연산을 적용해서 모든 요소들이 0이 되도록 해야한다.

한 번의 연산으로, [i, j]의 서브어레이를 정해서 음이 아닌 가장 작은 정수들을 0으로 바꿀 수 있다.

배열을 모두 0으로 바꾸기 위한 최소한의 연산 횟수를 구하시오.

 

풀이

부분배열을 고를 때, 0이 하나라도 들어있으면 안된다. 그 부분에 연산이 적용되기 때문이다.

모노토닉 스택으로 쉽게 구할 수 있다.

 

더 낮은 숫자보다 앞에 온 숫자들은, 어차피 별개의 연산을 거쳐야 한다.

즉, 연산을 적용했다치고 스택에서 제거하게 만들어서 이후 큰 수가 왔을 때에도 새로 연산을 적용하도록 해야 한다.

 

[1, 2, 1, 2, 1, 2]를 보자.

[0, 5] 구간에 연산을 적용하면, [0, 2, 0, 2, 0, 2]이다. 

이 2들은 사이에 0이 있기에, 모두 각각 적용해줘야 한다.

즉, 가장 작은 수 이전에 큰 수가 나오면, 이후에 그 큰 수가 나와도, 한번에 연산을 적용해줄 수 없다는 뜻이다.

 

스택을 단조 증가하는 형태로 유지하면, 이를 관리할 수 있다.

스택에서 이번에 확인할 수보다 큰 수들은 모두 pop하여 이후 그 수들이 나와도 같이 연산에 묻어갈 수 없게 말소시킨다.

그 뒤, 0이면 불필요하므로 스택에 넣지 않는다. 

만약, 스택이 비었거나 이번 수가 스택의 top보다 크다면, 연산횟수를 1 누적하고, 그때서야 top에 쌓아서 이후 연속으로 나오면서 연산을 묻어갈 수 있는 가능성을 남긴다.

 

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = []() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
class Solution {
   public:
    int minOperations(vector<int>& nums) {
        vector<int> stack;
        int ans = 0;
        for (int num : nums) {
            while (!stack.empty() && stack.back() > num) {
                stack.pop_back();
            }

            if (num == 0) continue;
            if (stack.empty() || stack.back() < num) {
                ans++;
                stack.emplace_back(num);
            }
        }

        return ans;
    }
};

 

Go

func minOperations(nums []int) int {
	stack := make([]int, 0, len(nums)/2)
	ans := 0

	for _, num := range nums {
		for len(stack) > 0 && stack[len(stack)-1] > num {
			stack = stack[0 : len(stack)-1]
		}

		if num == 0 {
			continue
		}

		if len(stack) == 0 || stack[len(stack)-1] < num {
			ans++
			stack = append(stack, num)
		}
	}

	return ans

}

 

Rust

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut stack = vec![0; 0];
        let mut ans = 0;

        for &num in &nums {
            while stack.len() > 0 && stack[stack.len() - 1] > num {
                stack.pop();
            }

            if num == 0 {
                continue;
            }

            if stack.is_empty() || stack[stack.len() - 1] < num {
                ans += 1;
                stack.push(num);
            }
        }

        ans
    }
}