665. 非递减数列

题目

给你一个长度为  n  的整数数组，请你判断在 最多 改变  1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的：  对于数组中所有的  i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

例

输入: nums = [4,2,3]

输出: true

解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

题解

数组

要保证能够修改一个元素就变成非递减数组需要满足条件

• 只有一个元素不满足非递减，即最多存在一个 nums[i] > nums[i+1]
• 在存在上面的情况的时候，nums[i] 需要尽可能大，也就是 nums[i] = nums[i+1]

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
  const n = nums.length;
  let cnt = 0;
  for (let i = 0; i < n - 1; ++i) {
    const x = nums[i],
      y = nums[i + 1];
    if (x > y) {
      cnt++;
      if (cnt > 1) {
        return false;
      }
      if (i > 0 && y < nums[i - 1]) {
        nums[i + 1] = x;
      }
    }
  }
  return true;
};

时间复杂度：O(n)，其中 n 是数组 nums 的长度。 空间复杂度：O(1)。