665. Non Decreasing Array

Medium

Description

給定整數陣列 nums，判斷是否能最多修改一個元素使其成為非遞減陣列（nums[i] <= nums[i+1]）。

Example:

Input: nums = [4,2,3] Output: true （將 4 改為 1 或 2）

Intuition#

核心思路：遍歷找到違反非遞減的位置（nums[i] > nums[i+1]），若超過一次就 false。只有一次時，嘗試「降低 nums[i]」或「提高 nums[i+1]」，看是否能修復。

遇到 nums[i] > nums[i+1] 時有兩種修復選擇：
- 把 nums[i] 降低到 nums[i+1]（需確保 nums[i-1] <= nums[i+1]）
- 把 nums[i+1] 提高到 nums[i]（需確保 nums[i] <= nums[i+2]）
優先嘗試降低 nums[i]（影響更小），若不行再提高 nums[i+1]

Approaches#

1: Count Violations + Validate#

概念: 找到第一個違反點，分別嘗試兩種修復後驗證整個陣列
時間複雜度: O(n) - 最多遍歷兩次
空間複雜度: O(1) - 不需額外空間

class Solution {
    fun checkPossibility(nums: IntArray): Boolean {
        var violationIdx = -1

        for (i in 0 until nums.size - 1) {
            if (nums[i] > nums[i + 1]) {
                if (violationIdx != -1) return false
                violationIdx = i
            }
        }

        if (violationIdx == -1) return true  // 已經是非遞減

        // 嘗試刪除 nums[violationIdx] 或 nums[violationIdx + 1]
        return isValid(nums, violationIdx) || isValid(nums, violationIdx + 1)
    }

    private fun isValid(nums: IntArray, skipIdx: Int): Boolean {
        var prev = Int.MIN_VALUE
        for (i in nums.indices) {
            if (i == skipIdx) continue
            if (nums[i] < prev) return false
            prev = nums[i]
        }
        return true
    }
}

⭐2: Greedy One-Pass#

概念: 遍歷時遇到違反，根據 nums[i-1] 與 nums[i+1] 的關係決定修改哪個，只允許修改一次
時間複雜度: O(n) - 一次遍歷
空間複雜度: O(1) - 只用常數變數

class Solution {
    fun checkPossibility(nums: IntArray): Boolean {
        var modified = false

        for (i in 0 until nums.size - 1) {
            if (nums[i] > nums[i + 1]) {
                if (modified) return false
                modified = true

                // 優先降低 nums[i]（影響範圍小）
                if (i == 0 || nums[i - 1] <= nums[i + 1]) {
                    nums[i] = nums[i + 1]
                } else {
                    // 無法降低 nums[i]，只能提高 nums[i+1]
                    nums[i + 1] = nums[i]
                }
            }
        }
        return true
    }
}

Greedy 選擇的關鍵：優先「降低 nums[i]」而非「提高 nums[i+1]」，因為降低不會影響後續元素的合法性。只有當 nums[i-1] > nums[i+1] 時才被迫提高 nums[i+1]。

🔑 Takeaways#

Pattern: 最多修改 k 次使陣列滿足某性質 -> Greedy 遍歷 + 計數修改次數
關鍵技巧: 遇到違反時分析「修改哪一端影響更小」，這是 Greedy 選擇的核心。注意修改是「就地修改」陣列，影響後續的判斷