665. 非递减数列

2018-06-04  本文已影响48人  吃饭用盘装

内容

给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。

示例 1:

输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
说明: n 的范围为 [1, 10,000]。


思路

既然是要做成一个非递减数列,那么就是 i1<=i2<=i3
如果不满足的话,那就需要分情况讨论,以下是不满足的所有组合:

  1. i1>i2<=i3
    这种情况直接让i1=i2即可,
    因为不管i1>i3还是i1<i3只要满足i1<=i2即可

2、 i1>i2>i3
这种情况无解

3、 i1<=i2>i3
假设有i1<=i2>i3<=i4
然后这里可能需要分两种情况:
1. 如果i1<i3,同时i3需要>=i2,也就是i1<=i2<=i3<=i4,然而事实是i3<i2,如果将i3=i2,那么i3会比之前变大,很可能会出现i3>i4的情况,所以这里只能选择将i2变小,因为i3也大于i1,所以i2变成i3还是能满足i2>=i1的条件。
2. 如果i1>i3,那么i3也要满足>=i2,所以这里只能i3=i2


代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function (nums) {
    var changeCount = 0;
    for (var i = 0; i < nums.length; i++) {
        var last = nums[i - 1] || -(Math.pow(2, 31) + 100);
        var next = nums[i + 1] || Math.pow(2, 31) + 100;

        if (last <= nums[i] && nums[i] > next) {
            if (changeCount > 0) return false;

            if (last < next) {
                nums[i] = next;
            } else {
                nums[i + 1] = nums[i];
            }

            changeCount++;
            i = -1;
        }

        if (last > nums[i] && nums[i] > next) {
            return false;
        }

        if (last > nums[i] && nums[i] <= next) {
            if (changeCount > 0) return false;
            nums[i] = last;
            changeCount++;
            i = -1;
        }
    }

    return true;
};

回到目录

上一篇 下一篇

猜你喜欢

热点阅读