665. Non-decreasing Array

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]）。

這種貪心策略確保修改後不會引入新的違反。

時間複雜度：O(n) — 單次遍歷陣列。

空間複雜度：O(1) — 只使用常數額外空間。

不修改原陣列：記錄違反位置 p，然後分別檢查「刪除 nums[p]」和「刪除 nums[p+1]」後的子陣列是否為非遞減。時間 O(n)，空間 O(1)。這種方法邏輯更清楚但需要兩次額外的線性掃描。

暴力法：對每個位置嘗試修改，然後檢查整個陣列。時間 O(n^2)，不推薦。

1. 如果允許最多修改 k 個元素呢？如何調整演算法？
2. 為什麼在 nums[i-1] > nums[i+1] 時要提升 nums[i+1] 而不是降低 nums[i]？
3. 這個問題和「最長非遞減子序列」有什麼關係？