【Leetcode Daily】3542将所有元素变为0的最少操作次数

发表于2025-11-10|更新于2025-11-10|力扣日常 | LeetcodeDaily

|总字数:301|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是就是给一个非负整数数组，每次可以选择其中一个子数组，并对其中的最小非负数置零，求将一个数组全部置零的最少操作次数。

思路分享

可以看到，子数组中不能有 0 ，否则操作无效（对 0 置零）所以就可以合并一段段相同的值，然后看整个数组有多少个不同的值，其中如果一个大值的左右都更小，说明这个大值必须单独占用一个操作，可以记录并弹栈。现在发现可以采用单调栈这个方式来处理这个问题。

https://leetcode.cn/problems/minimum-operations-to-convert-all-elements-to-zero/solutions/3673804/cong-fen-zhi-dao-dan-diao-zhan-jian-ji-x-mzbl/?envType=daily-question&envId=2025-11-10

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        st = [0]
        for i,x in enumerate(nums):
            while st and x < st[-1]:
                st.pop()
                ans += 1
            if not st or x != st[-1]:
                st.append(x)
        return ans + len(st) - 1 # 这里的 1 指单调栈最前面的 0

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/e14dc564.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 单调栈

相关推荐

【Leetcode Daily】1475商品折扣后的最终价格

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个商品价格列表，现在每个价格可以拥有优惠，即减去该商品之后最近的那个价格不大于自身的商品价格。求折扣后的商品价格列表。思路分享对于每个元素查找下一个比自己小的元素，很自然就想到可以用单调栈来处理，以参考题解的从左往右为例。只要在栈内存储比较大的，还没找到下个比自己小的元素，然后遍历新元素时，检查栈顶是否比自己大，是的情况就弹栈处理优惠，否则就直接压栈。代码解答（强烈建议自行解答后再看）参考题解 123456789class Solution: def finalPrices(self, prices: List[int]) -> List[int]: stk = [] ans = prices[:] for i, x in enumerate(prices): while stk and x <= prices[stk[-1]]: ans[stk.pop()] -= x ...

【Leetcode Daily】739每日温度

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组代表一组温度，求每个温度与下一次比当前温度大的天数之差。思路分享对于每个元素想要找各自的下一个更大或者更小的情况，可以通过单调栈来比较便利地解决。所谓单调栈，就是维护一个栈的单调性，使得其从栈顶到栈底是递增或者递减的关系。也就是只要维护已遍历的部分中的最大或者最小值（枚举的思路也有些相近）。具体的做法大致两个方法，但都是一个思路，就是去除无用信息，让程序尽快判断出代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314151617181920212223242526class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) stk = [] # 这个栈是存右侧的最大值下标的 right = [0] * n for i in range(n-1,...

【Leetcode Daily】1003检查替换后的词是否有效

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个字符串，该字符串是从一个空字符串开始，不断插入“abc”形成的，这个插入是从字符串的任意处都可以行动。思路分享这个题目和实际的题意完全不是一个意思，坏。不过这个不重要。发现做栈，只要把握一点，就是何时弹栈。例如本题，只要意识到，弹栈的时候，正在遍历的字母是 c，栈顶有 a 和 b，就轻松地写出了条件。这个条件应该不是最快的，因为只要中间的 abc 有一处无法正确匹配，就可以算是检测不过关，所以更快的思路应该是按照正在遍历的 abc 三种情况，分别检测栈是否符合“正常”。 https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions/solutions/2253773/zhan-jian-ji-xie-fa-pythonjavacgo-by-end-i9o7/ 本题不断插入 abc，并要求检测是否都是...

【Leetcode Daily】1004最大连续1的个数III

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个由 0 和 1 组成的整数数组，现在最多可以把其中 k 个 0 反转成 1。求反转后最长连续 1 的个数。思路分享纯粹的不定长滑动窗口（【Leetcode Daily】3090每个字符最多出现两次的最长字符串），无需多盐。代码解答（强烈建议自行解答后再看）陆爻齐的解法 1234567891011121314151617class Solution {public: int longestOnes(vector<int>& nums, int k) { int zero_count = 0; int left = 0; int n = nums.size(); int ans = 0; for (int i = 0; i < n;i++) { zero_count += 1-nums[i]; while(zero_count...

【Leetcode Daily】1021删除最外层的括号

题目浅析想查看原题可以点击题目链接。简单地说，就是按照题目规定的“原语”来分解有效的括号字符串，要求去掉最外面的一层括号。思路分享通过栈记录可以判定当前的括号是否为最外层。具体方法是记录符号时，如果栈内有括号，说明不是最外层，就记录到结果中，否则就只压栈。 https://leetcode.cn/problems/remove-outermost-parentheses/solutions/1520365/shan-chu-zui-wai-ceng-de-gua-hao-by-leet-sux0/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415class Solution: def removeOuterParentheses(self, s: str) -> str: res, stack = "", [] for c in s: print(res) print(stack) ...

【Leetcode Daily】1046最后一块石头的重量

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个一维数组，当作一堆石头重量，每次选两个最重的碰，将两个石头之差放回去，求最后剩下的一个石头重量（没有就0）思路分享这种多次求最值的，用堆，只是要记得，python的 heapify 默认最小堆，所以数字先做负数处理再堆化。 https://leetcode.cn/problems/last-stone-weight/solutions/540130/zui-hou-yi-kuai-shi-tou-de-zhong-liang-b-xgsx/ 代码解答（强烈建议自行解答后再看）参考题解 12345678910111213class Solution: def lastStoneWeight(self, stones: List[int]) -> int: for i in range(len(stones)): stones[i] = -stones[i] heapify(stones) while stones and...

数据加载中