解題說明
Non-decreasing Array
題目描述:給定一個整數陣列 nums,判斷是否能透過最多修改一個元素,使整個陣列變成非遞減(non-decreasing)序列。
解題思路:遍歷陣列,當發現 nums[i] > nums[i+1](違反非遞減)時,計數加一。若違反次數超過一次,直接回傳 false。
關鍵在於發現違反時,要決定修改 nums[i] 還是 nums[i+1]:
- 若
i == 0或nums[i-1] <= nums[i+1],將nums[i]降低為nums[i+1](優先降低前者,保持後面不受影響)。 - 否則,將
nums[i+1]提升為nums[i](因為降低前者會導致nums[i-1] > nums[i])。
這種貪心策略確保修改後不會引入新的違反。
C++ 解法
複雜度分析
時間複雜度:O(n) — 單次遍歷陣列。
空間複雜度:O(1) — 只使用常數額外空間。
虛擬碼
1. Initialize count = 0
2. For i from 0 to n-2:
a. If nums[i] > nums[i+1]:
- count++
- If count > 1, return false
- If i > 0 AND nums[i-1] > nums[i+1]:
- Set nums[i+1] = nums[i] (raise the smaller)
- Else:
- Set nums[i] = nums[i+1] (lower the larger)
3. Return true其他解法
不修改原陣列:記錄違反位置 p,然後分別檢查「刪除 nums[p]」和「刪除 nums[p+1]」後的子陣列是否為非遞減。時間 O(n),空間 O(1)。這種方法邏輯更清楚但需要兩次額外的線性掃描。
暴力法:對每個位置嘗試修改,然後檢查整個陣列。時間 O(n^2),不推薦。
延伸思考
- 如果允許最多修改 k 個元素呢?如何調整演算法?
- 為什麼在
nums[i-1] > nums[i+1]時要提升nums[i+1]而不是降低nums[i]? - 這個問題和「最長非遞減子序列」有什麼關係?