目标
给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。
在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。
返回使整个数组变为 0 所需的最少操作次数。
一个 子数组 是数组中的一段连续元素。
示例 1：
输入: nums = [0,2]
输出: 1
解释:
选择子数组 [1,1]（即 [2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为 [0,0]。
因此，所需的最少操作次数为 1。示例 2：
输入: nums = [3,1,2,1]
输出: 3
解释:
选择子数组 [1,3]（即 [1,2,1]），最小非负整数是 1。将所有 1 设为 0，结果为 [3,0,2,0]。
选择子数组 [2,2]（即 [2]），将 2 设为 0，结果为 [3,0,0,0]。
选择子数组 [0,0]（即 [3]），将 3 设为 0，结果为 [0,0,0,0]。
因此，最少操作次数为 3。示例 3：
输入: nums = [1,2,1,2,1,2]
输出: 4
解释:
选择子数组 [0,5]（即 [1,2,1,2,1,2]），最小非负整数是 1。将所有 1 设为 0，结果为 [0,2,0,2,0,2]。
选择子数组 [1,1]（即 [2]），将 2 设为 0，结果为 [0,0,0,2,0,2]。
选择子数组 [3,3]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,2]。
选择子数组 [5,5]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,0]。
因此，最少操作次数为 4。说明:
- 1 <= n == nums.length <= 10^5
- 0 <= nums[i] <= 10^5
思路
有一个非负整数数组 nums，每一次操作可以任选一个子数组，将子数组的最小非负整数设为 0，求将整个数组变为 0 所需的最小操作次数。
保存元素值与下标的映射，同时记录已经变为 0 的元素下标，按照元素值从小到大的顺序枚举对应的下标，同时判断该下标后面是否有已变为 0 的下标。
代码
/**
* @date 2025-11-10 8:53
*/
public class MinOperations3542 {
public int minOperations(int[] nums) {
TreeMap<Integer, List<Integer>> map = new TreeMap<>();
TreeSet<Integer> zeros = new TreeSet<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
int v = nums[i];
if (v == 0) {
zeros.add(i);
continue;
}
map.putIfAbsent(v, new ArrayList<>());
map.get(v).add(i);
}
int res = 0;
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
if (zeros.size() == 0) {
res++;
zeros.addAll(entry.getValue());
continue;
}
Integer right = null;
for (Integer index : entry.getValue()) {
if (right != null && index < right) {
continue;
}
res++;
right = zeros.higher(index);
if (right == null) {
break;
}
}
zeros.addAll(entry.getValue());
}
return res;
}
}
性能
