LeetCode 3542. Minimum Operations to Convert All Elements to Zero

May 12, 2025

biweekly contest 156。
挺難的，應該是能算上前幾難的 Q2。

題目

https://leetcode.com/problems/minimum-operations-to-convert-all-elements-to-zero/description/

解法

可以選 nums 的任意子陣列，把其中所有最小值變成 0。求最少需要幾次操作。
注意：若子陣列中最小值為 0，則操作沒有任何意義。

第一步操作很直覺，對整個 nums 操作，把所有最小值變成 0。
操作後 nums 一定會有 0，以 0 為邊界劃分出若干個不為 0 的子陣列。
得到規模更小的子問題，可以用遞迴分治解決。

對於子問題 nums[l..r]，我們需要：

找區間最小值 mn
找 nums[l..r] 哪些個索引是 mn，記做 pos

查詢區間最小值可以用線段樹。
mn 的位置只需要先預處理，按照 nums[i] 分組，然後二分找第一個 / 最後一個位置。

找到 pos 後，枚舉相鄰的兩個索引 a, b，其子問題為 nums[a+1..b-1]。
注意：若 pos[0] 不為 l，則有子問題 nums[l..pos[0]-1]；對於 r 同理。

時間複雜度 O(N log N)。
空間複雜度 O(N)。

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        N = len(nums)

        mp = defaultdict(list)
        for i, x in enumerate(nums):
            mp[x].append(i)

        def find_pos(x, l, r):
            pos = mp[x]
            i = bisect_left(pos, l)
            j = bisect_right(pos, r)
            return pos[i:j]

        seg = SegmentTree(N)
        seg.build(nums, 1, 0, N-1)

        def solve(l, r):
            if l > r:
                return 0

            mn = seg.query(1, 0, N-1, l, r)
            pos = find_pos(mn, l, r)
            cnt = 1 if mn > 0 else 0
            for a, b in pairwise(pos):
                cnt += solve(a+1, b-1)
            if pos[0] != l:
                cnt += solve(l, pos[0]-1)
            if pos[-1] != r:
                cnt += solve(pos[-1]+1, r)
            return cnt

        return solve(0, N-1)


class SegmentTree:

    def __init__(self, n):
        self.tree = [0]*(n*4)

    def build(self, init, id, L, R):
        """
        初始化線段樹
        若無初始值則不需執行
        """
        if L == R:  # 到達葉節點
            self.tree[id] = init[L]
            return
        M = (L+R)//2
        self.build(init, id*2, L, M)
        self.build(init, id*2+1, M+1, R)
        self.push_up(id)

    def op(self, a, b):
        """
        任意符合結合律的運算
        """
        return min(a, b)

    def push_up(self, id):
        """
        以左右節點更新當前節點值
        """
        self.tree[id] = self.op(self.tree[id*2], self.tree[id*2+1])

    def query(self, id, L, R, i, j):
        """
        區間查詢
        回傳[i, j]的總和
        """
        if i <= L and R <= j:  # 當前區間目標範圍包含
            return self.tree[id]
        res = inf
        M = (L+R)//2
        if i <= M:
            res = self.query(id*2, L, M, i, j)
        if M+1 <= j:
            res = self.op(res, self.query(id*2+1, M+1, R, i, j))
        return res

根據上述子問題處理方式，有個很重要的性質：

若某數 x 的左或右有更小的數，則 x 需要自己刪除一次

聽起來很像廢話。先看最簡單的例子：

nums = [1,2,3,3]

陣列嚴格遞增，操作次數等於不同元素個數。
再來看別的例子：

nums = [1,2,1,5,1,2]

被 1 分隔的元素都需要自己操作。

問題轉換成：每個元素找下一個更小的元素。
相似題 496. next greater element i。

維護嚴格單調遞增堆疊。
若當前元素 x 比堆疊頂端元素更小，代表頂端元素需要獨自操作。刪除頂端元素，操作次數加 1，直接滿足遞增為止。

刪除堆頂後，有時候相連的元素可以一起操作，例如：

nums = [2,2]
兩個 2 可一起操作
nums = [1,2,1]
2 刪掉之後剩下 [1,0,1]，兩個 1 可一起操作

只有在當前元素 x 與堆頂不同時才要加入。

遍歷結束後，堆疊中大小即不同元素個數，即所需操作次數。
記得特判 0 是否存在，因為 0 本身不需操作，操作次數需減 1。

時間複雜度 O(N)。
空間複雜度 O(N)。

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        st = []
        for x in nums:
            while st and x < st[-1]:  # 發現更小值，先前元素需操作
                ans += 1
                st.pop()
            if not st or st[-1] != x:  # 嚴格遞增，相同的元素可合併操作
                st.append(x)

        ans += len(st)
        if st[0] == 0:  # 原有的 0 不需操作
            ans -= 1

        return ans

mocowcow

題目

解法