非递减数列（665）

题目

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

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

示例

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

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

输入: nums = [4,2,1] 输出: false

解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明

• 1 <= n <= 10 ^ 4
• -(10 ^ 5) <= nums[i] <= 10 ^ 5

算法

计算峰谷数量

不满足非递增数列的元素会让所有值在坐标系中的连线呈现出波峰和波谷，而波峰和波谷都会有一段上坡和下坡组成，上坡满足非递增数列，那么我们判断下坡的情况即可，也就是峰谷差

我们可以考虑下面三种情况：

[4, 2, 3] //1
[1, 4, 2, 3]  // 2
[5, 7, 1, 8] // 3

第一种情况的峰谷差出现在4 2之间，此时我们需要降低波峰4——也就是说当nums[i] > nums[i+1]且nums[i-1]不存在时，我们让nums[i] = nums[i+1]

第二种情况的峰谷差出现在4 2之间，此时我们需要降低波峰4——也就是说当nums[i] > nums[i+1]且nums[i+1] >= nums[i-1]时，我们让nums[i] = nums[i+1]

第三种情况的峰谷差出现在7 1之间，此时我们需要升高波谷1——也就是说当nums[i] < nums[i+1]且nums[i+1] >= nums[i-1]时，我们让nums[i] = nums[i-1]

为了满足题目要求，整个数列中出现的峰谷差的数量不能大于1

export const checkPossibility = (nums) => {
	let changeCount = 1;
	for (let i = 1; i < nums.length; i++) {
    // 当第i个元素和i-1个元素对比递减时，我们向前判断i和i-2的关系
		if (nums[i] < nums[i - 1]) {
      // 当i-2个元素不存在或者i-2个元素小于等于第i个元素，我们要降低第i-1个元素
			if (i - 2 < 0 || nums[i - 2] <= nums[i]) {
				nums[i - 1] = nums[i];
			} else {
      // 否则当i-2个元素大于第i个元素时，我们要升高第i个元素
				nums[i] = nums[i - 1];
			}
			changeCount--;
		}
	}
	return changeCount >= 0;
};