• Leetcode 3510. Minimum Pair Removal to Sort Array II
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3510. Minimum Pair Removal to Sort Array II

1. 解題思路

這一題和題目3507. Minimum Pair Removal to Sort Array I本質上是同一道題目，唯一的區別在于時間復雜度的要求上面。

對于題目3507，我們可以通過一個二重循環進行實現，時間復雜度為$O(N^2)$，但是放到這里就顯然不行了，我們最多只能允許一個時間復雜度為$O(N?logN)$的算法實現。

而這里難度會有兩個：

1. 找到當前最小的相鄰元素的和，來進行元素的替換；
2. 如何判斷當前序列是否已經變成了一個單調非減的序列。

正常來說，這倆都需要$O(N)$的時間復雜度，但是，這里，我們需要對其進行優化。

首先，對于第一個問題，找到最小的相鄰元素的問題，我們可以通過二分搜索的方式實現，找最小的元素，其時間復雜度就是$O(logN)$，但是問題在于我們在合并之后其前后的元素會同時被調整，因此我們需要維護當前的數組，然后對其前后的元素的和進行同步調整。

而對于第二部分的問題，對于單調非減序列的判斷，正常確實需要$O(N)$的時間復雜度，但是這里我們可以通過維護當前數組當中相鄰元素的逆序元素的個數來進行判斷，對于單調非減序列，其逆序元素的總數必然為0。

因此，這就變成了一個數組的維護問題了。

唯一比較坑的是，如果直接使用二分查找的方式，會出現超時的情況，需要使用堆排來對其進行進一步的優化。

2. 代碼實現

給出最終的python代碼實現如下：

class Solution:def minimumPairRemoval(self, nums: List[int]) -> int:n = len(nums)index = [i for i in range(n)]pairs = [(nums[i] + nums[i+1], i) for i in range(n-1)]heapq.heapify(pairs)remove = set()reverse_cnt = 0for i in range(n-1):if nums[i] > nums[i+1]:reverse_cnt += 1m = nwhile reverse_cnt > 0:s, idx = heapq.heappop(pairs)if (s, idx) in remove:continueremove.add((s, idx))i = bisect.bisect_left(index, idx)# replace elementx, y = nums[i], nums[i+1]xi, yi = index[i], index[i+1]nums.pop(i+1)nums[i] = x+yindex.pop(i+1)m -= 1if x > y:reverse_cnt -= 1# maintain pre elementif i-1 >= 0:t, ti = nums[i-1], index[i-1]remove.add((t+x, ti))heapq.heappush(pairs, (t+x+y, ti))if (t+x+y, ti) in remove:remove.remove((t+x+y, ti))if t > x:reverse_cnt -= 1if t > x+y:reverse_cnt += 1# maintain post elementif i+1 < m:t, ti = nums[i+1], index[i+1]remove.add((t+y, yi))heapq.heappush(pairs, (t+x+y, xi))if (t+x+y, xi) in remove:remove.remove((t+x+y, xi))if y > t:reverse_cnt -= 1if x+y > t:reverse_cnt += 1return n - m

提交代碼評測得到：耗時7765ms，占用內存95.4MB。