665. 非递减数列（贪心算法）

665. 非递减数列

• 题目
• 解题思路
• 代码

题目

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

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

说明：

• 1 <= n <= 10 ^ 4
• 10 ^ 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;

    }
}