LeetCode Daily Problem P3542: Minimum Number of Operations to Make All Elements Zero

---

Timeline

timeline

2025-11-10

init

monotonic stack

---

Problem:

P3542 Make all elements become 0 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 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 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 identical numbers, then they cannot both be turned into 0 together.

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

• For each element a, if the top element of the stack is greater than a, according to Rule 2, the top element cannot be operated together with later elements, so we need to pop the top.
• 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;
	}
};