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 = arr
        self.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] = x
            else:
                self.root[x] = y
        return

class 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 = 0
        for x, i in nums:
            if x == 0:
                break
            need_op = True
            seen.add(i)
            if i-1 >= 0 and i-1 in seen:
                if dsu.find_elem(i-1) <= x:
                    need_op = False
                dsu.union(i-1, i)
            if i+1 < n and i+1 in seen:
                if dsu.find_elem(i+1) <= x:
                    need_op = False
                dsu.union(i+1, i)
            if need_op:
                ans += 1
        return ans

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