LeetCode Biweekly Contest 120 解題紀錄

第17次的LeetCode週賽，雖然沒 AK，但首次排名3位數，還是有點小開心的。

All problems solved by python

---

Q1: 🟢 2970. Count the Number of Incremovable Subarrays I 1563

tags: 暴力(Brute Force) 模擬(Simulation) 前後綴分解

題意

• 給定一個下標從 $0$ 開始的正整數陣列 nums。
• 如果 $nums$ 的一個子陣列滿足：移除這個子陣列後剩餘元素嚴格遞增，那麼我們稱這個子陣列為 移除遞增子陣列 。
  • 比方說，$[5, 3, 4, 6, 7]$ 中的 $[3, 4]$ 是一個移除遞增子陣列，因為移除該子陣列後，$[5, 3, 4, 6 , 7]$ 變成 $[5, 6, 7]$，是嚴格遞增的。
• 返回 $nums$ 中移除遞增子陣列的總數目。
• 注意，剩餘元素為空的陣列也視為是遞增的。
• 子陣列 指的是陣列中一段連續的元素序列。

限制

• $1 \leq nums.length \leq 50$
• $1 \leq nums[i] \leq 50$

思路：暴力模擬 / 前後綴分解

思路一：暴力模擬

• 由於數據範圍很小，枚舉要刪除的子陣列的左右邊界，然後檢查是否滿足條件即可。
• 時間複雜度 $O(n^3)$
• 空間複雜度 $O(1)$。

思路二：前後綴分解

賽時寫Q3時想到的，但 $O(n^2)$ 的複雜度在 Q3 還是會 TLE，所以放到Q1來說。

• 由於刪除後左右兩邊的數字都要是遞增的，因此我們可以先計算出 $nums$ 的前綴以及 $pre$ 和後綴 $suf$
  • $pre[i]$ 代表 $nums[:i+1]$ 是否滿足遞增。
  • $suf[i]$ 代表 $nums[i:]$ 是否滿足遞增。
• 刪除後仍是遞增，代表刪除後的左右子陣列都是遞增的，且左子陣列的最後一個元素小於右子陣列的第一個元素。因此枚舉要刪除的子陣列的左右邊界 $i$ 和 $j$，檢查 $pre[i-1]$、$suf[j+1]$ 是否為 $1$，且 $nums[i-1] < nums[j+1]$ 是否成立即可。注意一些邊界情況。
• 時間複雜度 $O(n^2)$
• 空間複雜度 $O(n)$。

暴力模擬前後綴分解

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        def check(i, j):
            cur = nums[:i] + nums[j + 1:]
            nn = len(cur)
            for k in range(nn - 1):
                if cur[k] >= cur[k + 1]:
                    return False
            return True
        n = len(nums)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                if check(i, j):
                    ans += 1
        return ans

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        pre = [1]
        for i in range(1, n):
            x = 1 if nums[i] > nums[i - 1] and pre[-1] else 0
            pre.append(x)
        suf = [1]
        for i in range(n - 2, -1, -1):
            x = 1 if nums[i] < nums[i + 1] and suf[-1] else 0
            suf.append(x)
        suf = suf[::-1]
        ans = 0
        for i in range(n):
            for j in range(i, n):
                if (i-1 < 0 or pre[i-1] == 1) and (j+1 >= n or suf[j+1] == 1) and (i-1 < 0 or j+1 >= n or nums[i-1] < nums[j+1]):
                    ans += 1
        return ans

---

Q2: 🟡 2971. Find Polygon With the Largest Perimeter 1521

tags: 排序(Sorting) 枚舉(Enumeration)

題意

• 給定一個長度為 $n$ 的正整數陣列 $nums$，表示可以選擇的邊長。
• 多邊形(Polygon)是一個至少有 $3$ 個邊的封閉平面圖形，且多邊形的最長邊小於其其他邊的總和。
• 如果有 $k$ ($k \geq 3$) 個正整數 $a_1$, $a_2$, $a_3$, …, $a_k$，其中 $a_1 \leq a_2 \leq a_3 \leq ... \leq a_k$ 且 $a_1 + a_2 + a_3 + ... + a_{k-1} > a_k$，那麼 必存在 一個具有 $k$ 邊的多邊形，其邊長為 $a_1$, $a_2$, $a_3$, …, $a_k$。
• 若 $nums$ 中的數字可以形成一個多邊形，返回能構造出的多邊形之 最大周長。若無法構造任何多邊形，返回 $-1$。

思路：排序 + 枚舉

• 由於題目已經說明了構成多邊形的條件，因此只要枚舉多邊形中最大的邊長，然後檢查是否能構成多邊形即可。我們可以先將 $nums$ 由小到大排序，然後從最大的邊長開始枚舉。
• 賽時用了前綴和來檢查是否大於其他邊的總和，但其實不需要，只需要先計算出所有邊的總和 $s$，然後檢查 $s - nums[i] > nums[i]$ ，再扣除當前邊長即可。
• 時間複雜度 $O(n \log n)$ ，排序的時間複雜度為 $O(n \log n)$，枚舉的時間複雜度為 $O(n)$。
• 空間複雜度 $O(1)$。

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        # pre = list(accumulate(nums, initial=0))
        s = sum(nums)
        for i in range(n - 1, 1, -1):
            # if pre[i] > nums[i]:
            #     return pre[i] + nums[i]
            if s  > 2 * nums[i]: # s - nums[i] > nums[i]
                return s
            s -= nums[i]
        return -1

---

Q3: 🔴 2972. Count the Number of Incremovable Subarrays II 2153

tags: 貪心(Greedy) 雙指標(Two Pointers) 前後綴分解

題意 (同Q1)

• 給定一個下標從 $0$ 開始的正整數陣列 nums。
• 如果 $nums$ 的一個子陣列滿足：移除這個子陣列後剩餘元素嚴格遞增，那麼我們稱這個子陣列為 移除遞增子陣列 。
  • 比方說，$[5, 3, 4, 6, 7]$ 中的 $[3, 4]$ 是一個移除遞增子陣列，因為移除該子陣列後，$[5, 3, 4, 6 , 7]$ 變成 $[5, 6, 7]$，是嚴格遞增的。
• 返回 $nums$ 中移除遞增子陣列的總數目。
• 注意，剩餘元素為空的陣列也視為是遞增的。
• 子陣列 指的是陣列中一段連續的元素序列。

限制

• $1 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$

思路：雙指標 (Two Pointers)

賽時沒做出來，看完靈神的講解後用原本的程式碼改了下，但還是沒有靈神的簡潔，就還是都放上來吧。

• 令 $i$ 作為左端點，代表刪除後左子陣列的最後一個元素的下標， $j$ 作為右端點，代表刪除後右子陣列的第一個元素的下標。
• 首先先確定 $i$ 的最右邊界，也就是 $nums$ 中前綴的最長遞增陣列的最後一個元素的下標。
  • 若 $i = n - 1$，代表整個陣列都是遞增的，因此每個子陣列都是可以被移除的，答案為 $n \times (n + 1) // 2$ ，直接特判。
• 首先處理右子陣列為空的情況，也就是 $j = n$，代表右子陣列為空，因此可以移除 $[0, n - 1]$、$[1, n - 1]$、…、$[i + 1, n - 1]$ 的子陣列，答案增加 $i + 2$。
• 固定右端點 $j$ ，若 $nums[i] < nums[j]$，代表可以移除 $[0, j - 1]$、$[1, j - 1]$、…、$[i + 1, j - 1]$ 的子陣列，答案增加 $i + 2$。
  • 若 $nums[i] \geq nums[j]$，代表左端點太大了，需要移動左端點 $i$，直到 $nums[i] < nums[j]$ 為止。
• 時間複雜度 $O(n)$
• 空間複雜度 $O(1)$。

前後綴分解 + 雙指標雙指標(簡潔版)

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        pre = [1]
        for i in range(1, n):
            x = 1 if nums[i] > nums[i - 1] and pre[-1] else 0
            pre.append(x)
        suf = [1]
        for i in range(n - 2, -1, -1):
            x = 1 if nums[i] < nums[i + 1] and suf[-1] else 0
            suf.append(x)
        suf = suf[::-1]

        i = pre.count(1) - 1 # 前綴最長遞增陣列的最後一個元素的下標
        if i == n - 1:
            return n * (n + 1) // 2
        ans = i + 2 # 可以移除 [0,n-1], [1,n-1], ..., [i+1, n-1] 的子陣列
        j = n - 1
        while j > 0 and suf[j] == 1: # 枚舉右端點
            while i >= 0 and nums[i] >= nums[j]: # 左端點太大了，移動左端點
                i -= 1
            ans += i + 2 # 可以移除 [0,j-1], [1,j-1], ..., [i+1, j-1] 的子陣列
            j -= 1
        return ans

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        while i < n - 1 and nums[i] < nums[i + 1]: # 先確定前綴的最長遞增陣列的最後一個元素的下標
            i += 1
        if i == n - 1: # 特判，整個陣列都是遞增的，代表每個子陣列都是可以被移除的
            return n * (n + 1) // 2

        ans = i + 2 # 可以移除 [0,n-1], [1,n-1], ..., [i+1, n-1] 的子陣列
        j = n - 1
        while j == n - 1 or nums[j] < nums[j + 1]: # 枚舉右端點
            while i >= 0 and nums[i] >= nums[j]: # 左端點太大了，移動左端點
                i -= 1
            ans += i + 2 # 可以移除 [0,j-1], [1,j-1], ..., [i+1, j-1] 的子陣列
            j -= 1
        return ans

類題

• 🟡 1574. Shortest Subarray to be Removed to Make Array Sorted 1932
  2972求數量，1574求長度
• 【题单】滑动窗口（定长/不定长/多指针）

參考資料

• 双指针，O(n) 时间 O(1) 空间（Python/Java/C++/Go）
• 【动画】一写就错？两种写法，总有一种适合你！（Python/Java/C++/Go）

---

Q4: 🔴 2973. Find Number of Coins to Place in Tree Nodes 2277

tags: DFS 貪心(Greedy) 樹上貪心 堆(Heap) 排序(Sorting)

題意

• 給定一棵有 $n$ 個節點的 無向樹，節點編號為 $0$ 到 $n - 1$，樹的根節點在節點 $0$ 處。 同時給定一個長度為 $n - 1$ 的二維整數陣列 $edges$，其中 $edges[i] = [a_i, b_i]$ 表示 樹中節點 $a_i$ 和 $b_i$ 之間有一條邊；以及一個長度為 $n$ 的整數陣列 $cost$，其中 $cost[i]$ 是第 $i$ 個節點的 花費。
• 在樹上每個節點放置金幣，在節點 $i$ 放置金幣的規則如下：
  • 如果節點 $i$ 的子節點數目小於 $3$，那麼在節點 $i$ 處放置 $1$ 個金幣。
  • 否則，計算節點 $i$ 對應的子樹內 $3$ 個不同節點的開銷乘積的 最大值 ，並在節點 $i$ 處放置對應數目的金幣。 如果最大乘積是 負數，那麼就放置 $0$ 個金幣。
• 返回一個長度為 $n$ 的整數陣列，其中第 $i$ 個元素是節點 $i$ 處放置的金幣數目。

思路：DFS + 貪心 + Heap/排序 + 啟發式合併 (樹上貪心)

• 由於題目要求的是最大值，因此可以使用貪心的思想，首先思考長度 $\geq 3$ 的陣列中，任取三數的最大正值為何
  • 若只考慮正數，且其中存在至少3個正數，最大的3個正數相乘，可能為最大值。
  • 若考慮負數，那麼最小的兩個負數乘最大的正數，也可能是最大值
  • 剩餘情況取三數相乘皆為負數。
• 因此在計算時，只需要考慮最大的3個正數以及最小的2個負數即可，向上傳遞時，只需要傳遞這5個數字即可。
• 以 DFS 訪問樹，對於每個節點，先計算子樹中的節點數量，以及子樹中的最大3個正數以及最小2個負數，然後向上傳遞。
• 由於題目要求的是最大值，因此可以使用 Heap 或排序的方式來計算最大3個正數以及最小2個負數。
  • Heap：將所有正數放入 MaxHeap，將所有負數放入 MinHeap，然後取前3大正數以及前2小負數。
  • 排序：將所有正數排序，取前3大正數，將所有負數排序，取前2小負數。
• 時間複雜度：
  • 排序：$O(n \log n)$ ，若合併時最多會有 n 個元素需要排序。
  • Heap： $O(n)$， heapify 的時間複雜度為 $O(n)$，取前三大/小的元素需要檢查5個元素，為了方便這邊直接取前3層的7個元素出來排序，時間複雜度視為 $O(7 \log 7) = O(1)$，因此總時間複雜度為 $O(n)$。 但是實測和排序差不多，可能是因為測資中大部分的點合併時都不超過7個元素，導致差別不大。
• 空間複雜度：$O(n)$

class Solution:
    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
        n = len(cost)
        g = defaultdict(list)
        for u, v in edges: # 無向圖
            g[u].append(v)
            g[v].append(u)

        ans = [1] * n # 初始化答案為1，即子樹中傑點數量 < 3 的情況

        def dfs(u, fa):
            res = 1 # 子樹中的節點數量
            hp1 = [-cost[u]] if cost[u] > 0 else [] # 正數，MaxHeap
            hp2 = [cost[u]] if cost[u] <= 0 else [] # 負數，MinHeap
            for v in g[u]:
                if v != fa:
                    x, res_hp1, res_hp2 = dfs(v, u)
                    res += x
                    hp1.extend(res_hp1)
                    hp2.extend(res_hp2)
            # Heap
            heapify(hp1) # O(n)
            heapify(hp2) # O(n)
            hp1 = sorted(hp1[:7])[:3] # 只取前3大正數，取前3層做排序
            hp2 = sorted(hp2[:3])[:2] # 只取前2小負數，取前2層做排序
            # 排序
            # hp1 = sorted(hp1)[:3] # 只取前3大正數
            # hp2 = sorted(hp2)[:2] # 只取前2小負數
            if res >= 3:
                tmp1 = tmp2 = float('-inf')
                if len(hp1) >= 3: # 三正
                    tmp1 = -hp1[0] * -hp1[1] * -hp1[2]
                if len(hp1) >= 1 and len(hp2) >= 2: # 一正兩負
                    tmp2 = -hp1[0] * hp2[0] * hp2[1]
                ans[u] = max(0, tmp1, tmp2) # 剩餘情況都是負數，根據題意，放0
            return res, hp1, hp2
        dfs(0, -1)
        return ans

---