leetcode每日一题 P3542 将所有元素变为 0 的最少操作次数

---

时间轴

2025-11-10

init

---

题目：

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

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

滑动窗口 TLE

用滑动窗口模拟会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)
	{
		// 滑动窗口
		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);
}

单调栈

正确做法是单调栈：

• 规律一：把若干相同的最小值同时变为 0，可以节省操作次数。
• 规律二：如果两个相同的数之间有更小的数，则他们一定不同一起被变为 0。
  我们遍历数组，维护一个单调递增栈，表示当前递增的非零元素序列。
  对于每个元素 a，如果栈顶元素大于 a，根据规律二，栈顶元素不可能和之后的元素一起操作，需要弹出栈顶。
  如果 a 已经为 0，跳过，因为已经不需要操作。
  如果栈为空或栈顶元素小于 a，说明我们需要新的一次操作来覆盖 a，并把它加入栈，并把操作次数加一。

把数组看成一个柱状图：

nums = [1,3,2,1]
高度变化如下：
1 ↑ 3 ↓ 2 ↓ 1 ↓ 0

每次操作像是从下往上“削一层”：

• 当高度上升：你需要一次新操作（开新的层）
• 当下降：说明前一层结束（栈顶出栈）

举例：

元素 a	栈 s 内容	说明	res
1	[] → [1]	新高度出现 → 新操作	1
3	[1] → [1,3]	高度上升 → 新操作	2
2	[1,3] → [1]（弹出 3）→ [1,2]	高度下降 → 结束 3 那层 → 相比于栈顶大：新操作	3
1	[1,2] → [1]（弹出 2）→ [1]	已存在同高度，不新加	3

另一个例子

元素 a	栈变化	说明	res
2	[] → [2]	新层	1
2	[2]	一样高，不变	1
3	[2,3]	上升，新层	2
3	[2,3]	一样高，不变	2
2	[2,3] → [2]	下降，结束 3 那层	2

#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;
	}
};