【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】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】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】1052爱生气的书店老板

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个整型数组，以及一个整数 minutes，按某个要求（具体看原题，难以简化），求一个数组在另一个数组和 minutes 约束下的求的最大值。思路分享陆爻齐的思路是计算窗口内（也就是冷静的分钟）不满意生气离开的最大值，加上不生气的心情值，再减去所有生气离开的数值得出答案，但由于思想复杂了点，所以略微修改模板结构，也就是下面陆爻齐的答案。参照灵茶山艾府，其实只要区分开两部分相加即可，然后直接参照模板。这两部分，一个是不生气的值，一个是生气下的值，取生气下最大值即可。这样就不用像上面一样多一次运算。 https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/2751888/ding-chang-hua-dong-chuang-kou-fu-ti-dan-rch7/ 代码解答（强烈建议自行解答后再看）陆爻齐的解法 12345678910111213141516171819202122232425class Solution...

【Leetcode Daily】1297子串的最大出现次数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个字符串，求满足要求的子串中，出现最多的次数。该要求为 1. 内部的字母数量小于 maxLetters；2. 整个字符串的长度在 minSize 和 maxSize 之间（闭区间）。思路分享该题的难度在于干扰项 maxSize，由于求子串尽可能多的出现，所以该子串的长度必然越小越好，就是 minSize。就是定长滑动窗口(【Leetcode Daily】1456定长子串中元音的最大数目)，有了个字母数量不大于 maxLetters 的限制，再用哈希统计满足要求字符串出现的次数即可。代码解答（强烈建议自行解答后再看）陆爻齐的解法 1234567891011121314151617181920212223242526272829class Solution {public: int maxFreq(string s, int maxLetters, int minSize, int maxSize) { vector<int>...

【Leetcode Daily】1423可获得的最大点数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个整型数组和一个数字 k，求按照某种方式下获取卡牌所得的最大点数。该方式为每次只能够取得最左或者最右的卡牌。思路分享逆向思路，由于每次拿卡牌只拿两侧，所以中间部分是连续的，可以视为一个定长滑动窗口，只不过是求窗口内的最小和，通过这个数值得到答案。滑动窗口模板沿用【Leetcode Daily】1456定长子串中元音的最大数目正向思路，穷举所有组合可能。 https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/solutions/2551432/liang-chong-fang-fa-ni-xiang-si-wei-zhen-e3gb/ 代码解答（强烈建议自行解答后再看）逆向 12345678910111213141516171819202122232425class Solution {public: int maxScore(vector<int>& cardPoints,...

【Leetcode Daily】1343大小为K且平均值大于等于与之的子数组数目

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个整数数组，两个整数 threshold 和 k。k是限定子数组的长度，threshold 是阈值。求这个数组中长度为 k 且平均值大于阈值 threshold 的数目。注意，在算法题中，子数组默认连续，而子序列默认不连续。思路分享定长滑动窗口模板秒了,具体参照【Leetcode Daily】1456定长子串中元音的最大数目不过这里的和用 int 也没问题，我估计是因为是大于等于阈值这个条件的关系，大于的情况即使因为整数的小数丢失，也能算做等于情况计入。代码解答（强烈建议自行解答后再看）滑动窗口 1234567891011121314151617181920class Solution {public: int numOfSubarrays(vector<int>& arr, int k, int threshold) { int result = 0; int sum = 0; for (int i =...

数据加载中