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;
};

参考资料