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

快来打我* 2023-10-05 12:10 8阅读 0赞

#### 665. 非递减数列 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

说明：

*  1 <= n <= 10 ^ 4
 *  10 ^ 5 <= nums\[i\] <= 10 ^ 5  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70_pic_center]

## 解题思路 ##

*  这题意思主要是：“给你一个数组，改变最多其中的一个元素能否让其成为非递减的数组 **非递减的意思就是相等或者递增**”
 *  我们当遇到 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;
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201021202332867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70#pic_center