665. Non-decreasing Array

Leetcode 問題: 665. Non-decreasing Array
Categories:
Tags:

題目

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

傳入一個 整數陣列 nums，最多 只能修改 1 個元素，讓整個整數陣列 nums變成非遞減陣列 (non-decreasing)

非遞減陣列 (non-decreasing)

遞增 與 相同 都是 非遞減 (non-decreasing)

遞增

  • [1, 2, 3, 5]

相同

  • [1, 1, 1]
  • [1, 3, 3, 5]

以上都是 非遞減 (non-decreasing) 陣列

Example

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Input: nums = [4,2,1]
Output: false
Explanation: You can\'t get a non-decreasing array by modify at most one element.

演算法

1. 檢查每一個 數字的前後 是否是 非遞減 狀況

目前數字 必須大於等於 前一個數字，才能是 非遞減 狀況

2. 若是 遞減 的狀況，則表示必須要修改其中之一的數字，讓他維持 非遞減 狀況

A. 將「前一個數字」設定為跟「目前數字」相同

  • 如果沒有「前前一個數字（索引小於 0）」，表示只有兩個數字可以做比較參考，「目前數字」跟「前一個數字」
    • 為了維持 非遞減 狀況，所以 「目前數字」必須變成大於或等於「前一個數字」
    • 但為了能夠讓後面的數字更容易維持在 非遞減 狀況，將「前一個數字」變成等於「目前數字」 可以提高整個數列維持 非遞減 狀況的機率
    • e.g. [7 5] => [5 5]
  • 如果有 「前前一個數字」，但「前前一個數字」 小於 「目前數字」
    • 「前前一個數字」 與 「前一個數字」 是 非遞減 狀況
    • 「前前一個數字」 與 「目前數字」 也是 非遞減 狀況
    • 所以 「前一個數字」與「目前數字」都可以保持與 「前前一個數字」維持 非遞減 狀況，那就選擇數字比較小的那一個，選擇「目前數字」可以提高整個數列維持 非遞減 狀況的機率
    • e.g. [4 7 5] => [4 5 5]

B. 將「目前數字」設定為跟「前一個數字」相同

  • 「前前一個數字」 與 「前一個數字」 是 非遞減 狀況
  • 「前前一個數字」 與 「目前數字」 不是 非遞減 狀況，是 遞增 狀況
  • 為了讓整個數列變成 非遞減 狀況，勢必要修改 「目前數字」，所以「目前數字」必須要大於等於 「前一個數字」 才能夠維持 非遞減 狀況
    • 將「目前數字」變成等於「前一個數字」 可以提高整個數列維持 非遞減 狀況的機率
    • e.g. [4 7 3] => [4 7 7]

3. 修改超過 1 次直接跳出

因為題目訂定說，只能修改 1 個元素，所以當遇到需要第 2 次修改時，直接跳出不用檢查，不符合題目的限制

答案

JavaScript

/**
 * @param {number[]} numsList
 * @return {boolean}
 */
var checkPossibility = function(numsList) {
    // 刪除的數量
    let deleteNumberCount = 0;

    // 從索引 1 開始比較，自己跟自己比較無法知道是「遞增」還是「遞減」
    for (let i = 1; i < numsList.length; i++) {
        // 目前數字
        let currentNumber = numsList[i];
        // 前一個數字
        let previousNumber = numsList[i-1];

        if (currentNumber < previousNumber) {
            // 如果「目前數字」小於「前一個數字」，一定不是「非遞減」數列
            // 至少需要刪除一個數字，讓他變成「非遞減」數列
            deleteNumberCount++;
            if (deleteNumberCount > 1) {
                // 若刪除的整數數量大於 1，無法符合條件在僅刪除一個數字，變成「非遞減」數列
                return false;
            }

            // 前前一個數字索引
            let previousPreviousNumberIndex = i - 2;
            // let previousPreviousNumber
            if (previousPreviousNumberIndex < 0 || numsList[previousPreviousNumberIndex] <= currentNumber) {
                // 如果沒有「前前一個數字（索引小於 0）」
                // 或者有「前前一個數字」，但是「前前一個數字」小於「目前數字」
                // 將「前一個數字」設定為跟「目前數字」相同
                //  - [7 5] => [5 5]
                //  - [4 7 5] => [4 5 5]
                numsList[i-1] = numsList[i];
            } else {
                // 將「目前數字」設定為與「前一個數字」相同
                // - [4 7 3] => [4 7 7]
                numsList[i] = numsList[i-1];
            }
        }
    }

    return true;
};

參考資料