LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.10
• 题目：3542. 将所有元素变为0的最少操作次数
• 难度：中等
• 标签: 数组、贪心、栈
• 题目链接：LeetCode 3542. 将所有元素变为0的最少操作次数

1. 题目理解

问题描述

给你一个大小为 n 的非负整数数组 nums，你需要执行若干次操作，使得所有元素都变为 0。每次操作的规则是：选择一个子数组 [i, j]（0 ≤ i ≤ j < n），将该子数组中所有最小的非负整数设为 0。返回使整个数组变为 0 所需的最少操作次数。

关键说明

• 子数组是连续的元素片段；
• 每次操作仅针对当前子数组中的「最小非负整数」，而非全局最小；
• 目标是通过最少的操作次数让所有元素归零。

示例

示例 1

输入: nums = [0, 2] 输出: 1 解释: 选择子数组 [1, 1]（即元素 2），其最小非负整数为 2，将其设为 0 后数组全为 0，仅需 1 次操作。

示例 2

输入: nums = [3, 1, 2, 1] 输出: 3 解释:

1. 第一次操作：选择子数组 [0, 3]（全局最小非负整数为 1），将所有 1 设为 0，数组变为 [3, 0, 2, 0]；
2. 第二次操作：选择子数组 [2, 2]（当前最小非负整数为 2），将 2 设为 0，数组变为 [3, 0, 0, 0]；
3. 第三次操作：选择子数组 [0, 0]（当前最小非负整数为 3），将 3 设为 0，数组全为 0。 总操作次数为 3。

示例 3

输入: nums = [2, 2, 3, 1, 2, 1, 2] 输出: 5

2. 解题思路

初始思路（TreeSet 分层处理）

核心观察

• 每次操作只能处理当前的「最小非负整数」，因此按数值从小到大分层处理是合理的（先处理最小的，再处理次小的，直到所有元素归零）；
• 同一层级的相同数值，若处于连续的非零段中，可通过一次操作批量置零，减少操作次数。

算法步骤

1. 收集非零值并排序：使用 TreeSet 收集数组中所有非零元素，利用其自动去重和升序排序的特性，得到从小到大的待处理数值序列；
2. 分层处理每个数值：遍历排序后的数值，对每个数值 val：
   • 遍历数组，寻找包含 val 的连续非零段；
   • 每找到一个连续段，操作次数加 1，并将该段内所有 val 置为 0；
3. 返回总操作次数。

优化思路（单调栈最优解）

核心规律提炼

通过分析题目本质，发现两个关键规律：

• 规律 1：相同的最小值若处于连续非零段中，可通过一次操作批量置零，节省次数；
• 规律 2：若两个相同数值之间存在更小的数值，则这两个数值无法在同一次操作中置零（因为更小的数值会先被处理，分割原连续段）。

算法步骤

1. 维护单调递增栈：栈中存储当前需要独立操作的「数值层级」，确保栈内元素严格递增（无重复、不递减）；
2. 遍历数组处理每个元素：
   • 若栈顶元素大于当前元素 a，说明栈顶元素的层级已被 a 覆盖（a 更小，会先处理，分割栈顶元素的连续段），弹出栈顶；
   • 若 a 为 0，直接跳过（已满足目标状态）；
   • 若栈为空或栈顶元素小于 a，说明 a 是新的「最小非负数值层级」，需要新增一次操作，将 a 入栈并累加操作次数；
3. 返回总操作次数。

3. 初始代码实现（TreeSet 版本）

import java.util.TreeSet;

class lc3600_lc3699.lc3660.Solution {
    public static int minOperations(int[] nums) {
        Integer res = 0;
        TreeSet<Integer> set = new TreeSet<Integer>();
        // 1. 收集所有非零元素，自动去重并升序排序
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                set.add(nums[i]);
            }
        }
        // 2. 按从小到大的顺序处理每个数值层级
        for (int val : set) {
            // 遍历数组寻找包含当前val的连续非零段
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == 0) continue; // 跳过已置零的元素
                // 找到当前val的起始位置，触发一次操作
                if (nums[j] == val) {
                    res++;
                    nums[j] = 0; // 标记当前位置为0
                    // 扩展连续段，将段内所有val置为0
                    int k = j + 1;
                    while (k < nums.length && nums[k] >= val) {
                        if (nums[k] == val) {
                            nums[k] = 0;
                        }
                        k++;
                    }
                }
            }
        }
        return res;
    }
}

4. 优化代码实现（单调栈版本，官方最优解）

import java.util.ArrayList;
import java.util.List;

class lc3600_lc3699.lc3660.Solution {
    public int minOperations(int[] nums) {
        // 单调递增栈：存储需要独立操作的数值层级（严格递增，无重复）
        List<Integer> stack = new ArrayList<>();
        int res = 0; // 记录最少操作次数

        for (int a : nums) {
            // 维护栈的单调递增性：弹出所有大于当前元素的栈顶
            // 原因：栈顶元素的层级被当前更小的a覆盖，无法与后续元素批量操作
            while (!stack.isEmpty() && stack.get(stack.size() - 1) > a) {
                stack.remove(stack.size() - 1);
            }
            if (a == 0) continue; // 跳过已置零的元素
            // 栈为空或栈顶元素小于当前a：新增操作层级
            if (stack.isEmpty() || stack.get(stack.size() - 1) < a) {
                res++;
                stack.add(a);
            }
        }
        return res;
    }
}

5. 复杂度分析

初始代码（TreeSet 版本）

• 时间复杂度：O(n log n + n * k)，其中 n 为数组长度，k 为非零不同数值的个数。TreeSet 插入和排序的时间为 O(n log n)，后续两层循环的时间为 O(n * k)（最坏情况下 k = n，时间复杂度退化为 O(n²)）；
• 空间复杂度：O(k)，TreeSet 存储非零不同数值，空间开销为 O(k)。

优化代码（单调栈版本）

• 时间复杂度：O(n)，每个元素入栈和出栈各一次，遍历数组仅需一次，整体为线性时间；
• 空间复杂度：O(k)，栈的最大长度不超过非零不同数值的个数 k（最坏情况下 k = n，空间复杂度为 O(n)）。

6. 总结

核心思路对比

• 初始思路（TreeSet）：通过分层处理数值，明确每个层级的连续段操作，逻辑直观但效率较低，适合理解题目本质；
• 优化思路（单调栈）：提炼题目核心规律，用单调栈维护「操作层级」，避免重复遍历和无效操作，实现线性时间复杂度，是最优解法。

关键收获

1. 单调栈的应用场景：当问题涉及「层级划分」「连续段判断」且需要维护递增/递减特性时，单调栈是高效工具；
2. 规律提炼的重要性：通过分析题目本质规律（如相同数值被更小数值分割后需独立操作），可大幅简化算法逻辑；
3. 避免修改原数组：初始版本直接修改原数组，可能导致后续逻辑依赖错误，优化版本用栈维护状态，更安全且高效。

适用场景扩展

该题的单调栈思路可迁移到类似「分层处理」「连续段统计」的问题中，例如：

• 统计数组中需要独立操作的递增/递减段数；
• 批量处理相同元素时，考虑中间是否有更小/更大元素分割。