Leetcode 3542. Minimum Operations to Convert All Elements to Zero

• Leetcode 3542. Minimum Operations to Convert All Elements to Zero
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3542. Minimum Operations to Convert All Elements to Zero

1. 解题思路

这一题的处理方法其实还是挺好想明白的，其实就是从小到大依次处理各个元素，对于每一个元素，将其前后连续的所有不小于该元素的节点连成一个连续子序列，然后对其进行统一操作，这样就能最优化地将所有元素均变为0。

但是这里的问题就在于说如何快速找出这连续的子序列，如果最暴力的走将会是一个$O(N^2)$的算法复杂度的实现了。

这里，我们采用的方法是使用DSU的方法，然后处理方式上从大到小依次处理元素，考察每一个元素时，我们只需要考察其前后的元素是否有被处理过，如果处理过的情况下，其所处的连续簇当中是否有过相同大小的元素，如果有，就可以将其合并，如果没有，那么则必须额外增加一次操作来处理当前的元素。

由此，我们即可得到最优的操作数。

2. 代码实现

给出python代码实现如下：

class DSU:def __init__(self, arr):self.arr = arrself.root = [i for i in range(len(arr))]def find(self, k):if self.root[k] != k:self.root[k] = self.find(self.root[k])return self.root[k]def find_elem(self, k):return self.arr[self.find(k)]def union(self, a, b):x = self.find(a)y = self.find(b)if x != y:if self.arr[x] <= self.arr[y]:self.root[y] = xelse:self.root[x] = yreturnclass Solution:def minOperations(self, nums: List[int]) -> int:n = len(nums)dsu = DSU(nums)seen = set()nums = sorted([(x, i) for i, x in enumerate(nums)], reverse=True)ans = 0for x, i in nums:if x == 0:breakneed_op = Trueseen.add(i)if i-1 >= 0 and i-1 in seen:if dsu.find_elem(i-1) <= x:need_op = Falsedsu.union(i-1, i)if i+1 < n and i+1 in seen:if dsu.find_elem(i+1) <= x:need_op = Falsedsu.union(i+1, i)if need_op:ans += 1return ans

提交代码评测得到：耗时1674ms，占用内存47.3MB。