Leetcode # 1909. Remove One Element to Make the Array Strictly Increasing

https://leetcode.com/problems/remove-one-element-to-make-the-array-strictly-increasing

Solution

n := len(nums)
Ni := nums[i]
i := [1, n – 1]

「如果我們從 nums 刪除一個節點後，nums 為嚴格遞增」

如果 nums 原本不是嚴格遞增
但符合題目條件（刪除一個節點後 nums 為嚴格遞增）
被刪除的那個節點與其相鄰兩點有下圖兩種情形
令 nums[i] 為唯一非嚴格遞增 ≡ not(nums[i – 1] < nums[i] < nums[i + 1])
≡ nums[i – 1] >= nums[i] or nums[i] >= nums[i + 1]
又只有 nums[i] 非嚴格遞增
（nums[i – 1] 和 nums[i + 1] 皆遵守嚴格遞增 ⇒ nums[i – 1] < nums[i + 1]）
⇒ nums[i + 1] > nums[i – 1] >= nums[i] （同時小於等於前後）
or nums[i] >= nums[i + 1] > nums[i – 1] （同時大於等於前後）

而兩種情形都會有 Ni – 1 >= Ni 的狀況發生
又可以再分為：
a. Ni > Ni – 2 ⇒ 刪除 Ni – 1
b. Ni – 1 > Ni – 2 >= Ni ⇒ 刪除 Ni
c. i – 1 == 0 ⇒ 刪除 Ni – 1
d. i == n – 1 ⇒ 刪除 Ni
但因為問題是「是否只要刪一個 num 就能讓 nums 為 strictly increasing」
 i 已經遍歷過整個 nums，所以刪除 Ni 還是 Ni – 1 已不太重要
（對 a, b, c 而言，刪掉哪一個 num 會影響之後的結果，但 d 後面已經不需要計算）

removed := already removed another num before
如果 removed 為 true 時
我們又找到另一個 Ni >= Ni + 1
⇒ 要使 nums 變成 strictly increasing
必須刪除兩個以上的 num ⇒ return False

刪掉一個 num 後
如果不讓被刪掉的該 num
脫離if nums[i - 1] >= nums[i]:的視野
可能會使下一個nums[i]判斷錯誤

例：[2, 3, 1, 2]

  • i = 2: nums[1] (3) > nums[2](1)
    ⇒ nums[0] (2) > nums[2] (1) ⇒ 刪去 nums[2] (1)
  • 如果 nums[2] (1) 沒有脫離視野
    則下一次判斷if nums[i - 1] >= nums[i]:
    會變成 nums[2] (1) < nums[3] (2) ⇒ False
    而不是 nums[1] (3) >= nums[3] (2) ⇒ True

如果實際地將目標從 nums 刪去
(nums_ = nums_[:i] + nums[i + 1:])
⇒ 會額外耗費 O(n) 的 space complexity

所以我們改以prev記錄理論上的前一個 num
（當 nums[i] 被刪除 ⇒ prev ← nums[i – 1] 否則 nums[i] ）

Time Complexity: O(n)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def canBeIncreasing(self, nums: List[int]) -> bool:
    removed, prev = False, nums[0]
    for i in range(1, len(nums)):
      if prev < nums[i]: 
        prev = nums[i]
        continue

      if removed: return False
      prev = nums[i - 1] if i >= 2 and nums[i - 2] >= nums[i] else nums[i]
      removed = True
        
    return True

 

Last Updated on 2023/08/18 by A1go

目錄

→ 目錄
Bitnami