665. 非递减数列

题目解题思路代码

题目

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

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

说明：

1 <= n <= 10 ^ 410 ^ 5 <= nums[i] <= 10 ^ 5

解题思路

这题意思主要是：“给你一个数组，改变最多其中的一个元素能否让其成为非递减的数组 非递减的意思就是相等或者递增”

我们当遇到 i-1>i的时候 就是出现了乱序，这个时候一般考虑缩小i-1，即令i-1=i（前提是i>i-2）。这样能最大限度的保证不影响i后面的元素。如果i=i-1，扩大了i，就有可能让i>i+1了。

当然有一种情况要例外，就是i-1>i,且i-2>i。这个时候就必须要i=i-1，只有这样才能保证i>i-2。

代码

class Solution { public boolean checkPossibility(int[] nums) { int count = 0; for(int i = 1;i < nums.length;i++){ if(nums[i -1] <= nums[i]){ continue;//如果是非递减（递增或者相等）的则直接进行下一次循环 } count++;//只要不满足非递减（递增或者相等）就必须执行这句代码 if(i - 2 >= 0 && nums[i-2] > nums[i]){//这种情况是突然遇到了i比i-1小，同时小于i-2 nums[i] = nums[i - 1];//必须要让i=i-1，只有这样才能保证i不小于i-2。 } else{//这种情况是i<i-1,但是i>i-2 nums[i-1] = nums[i];//让i-1=i;即把i-1缩小，因为I>i-2,所以不必担心前面的非递减性，之所以是缩小i-1，而不是让i=i-1;是为了避免i过大大于i+1. } } return count <= 1; } }