LeetCode Daily Challenge P3542 Minimum Number of Operations to Make All Elements 0

---

Timeline

Timeline

2025-11-10

init

Monotonic stack

---

Problem:

P3542 turn all elements into 0 the minimum number of operations

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

Sliding window TLE

Simulating with a sliding window will TLE

#include <vector>
#include <climits>
using std::vector;

class Solution {
    public:
	void ops(vector<int> &nums, int start, int end)
	{
		int i;
		int min = INT_MAX;
		for (i = start; i < end; i++) {
			if (nums[i] < min) {
				min = nums[i];
			}
		}
		for (i = start; i < end; i++) {
			if (nums[i] == min) {
				nums[i] = 0;
			}
		}
	}
	int minOperations(vector<int> &nums)
	{
		// Sliding window
		int left = 0, right = 0;
		int n = nums.size();
		int res = 0;
		while (left < n) {
			while (left < n && nums[left] == 0) {
				left++;
			}
			right = left;
			while (right < n && nums[right] > 0) {
				right++;
			}
			// [left, right)
			if (left == right && left == n) {
				break;
			}
			ops(nums, left, right);
			res++;
			//left = right;
		}
		return res;
	}
};

int main()
{
	vector<int> nums = { 1, 2, 1, 2, 1, 2 };
	Solution S;
	S.minOperations(nums);
}

Monotonic stack

The correct approach is a monotonic stack:

• Rule 1: Turning several identical minimum values to 0 at the same time can save operations.
• Rule 2: If there is a smaller number between two equal numbers, they cannot be turned to 0 together.

We traverse the array and maintain amonotonically increasing stack, indicatingcurrent increasing sequence of non-zero elements。

• For each element a, if the top of the stack is greater than a, according to Rule 2, the top element cannot be operated on together with later elements, so the top needs to be popped.
• If a is already 0, skip it because no operation is needed.
• If the stack is empty or the top element is less than a, it means we need a new operation to cover a, push it onto the stack, and increment the operation count by one.

#include <stack>
#include <vector>
using std::vector;
using std::stack;

class Solution {
    public:
	int minOperations(vector<int> &nums)
	{
		stack<int> s;
		int res = 0;
		for (int a : nums) {
			while (!s.empty() && s.top() > a) {
				s.pop();
			}
			if (a == 0)
				continue;
			if (s.empty() || s.top() < a) {
				res++;
				s.push(a);
			}
		}
		return res;
	}
};