題目描述:給定一個整數陣列 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])。這種貪心策略確保修改後不會引入新的違反。
時間複雜度: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),不推薦。
nums[i-1] > nums[i+1] 時要提升 nums[i+1] 而不是降低 nums[i]?