刷题之旅从数组类型的题目开始。第三十道题目是非递减数列，对应leetcode的题号为665。

image

题目描述

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

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

示例 1:

1
2
3
输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:

1
2
3
输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明:  n 的范围为 [1, 10,000]。

解题思路

只调整一次元素就成为非递减序列？我们考虑简单情况，比如示例的[4,2,3]，此时我们知道只需要调整4即可，比如[2,2,3]即可满足非递减序列要求，那么这个序列是符合条件的。但是[4,2,1]就不行，按照刚才的做法，第一步是[2,2,1]，但是此时第二个元素还是大于第三个元素，因此还要调整一次才符合，那么这个序列就不符合条件。

显然，这里的关键点是判断前一个元素是否大于后一个元素。一旦有此时就需要进行调整了。

不过如何调整呢？这里就稍微要注意点了，分为两种情况。以[i-1,i.i+1]为例，此时i处元素大于i+1处元素的：

  • 当i-1大于i+1元素的时候，比如[3,4,1]这里的策略是将1调整为4（这是比较简单的调整策略，调整为5的话可能会加重后续的调整），调整之后变成[3,4,4]即可满足
  • 当i-1小于i+1元素的时候，比如[1,4,3]这里策略是将4调小为3，变成[1,3,3]即可满足条件

具体见代码。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public boolean checkPossibility(int[] nums) {
        if(nums.length < 3){
            return true;
        }
        int count = 0;
        // 如果第一个元素大于第二个元素，那么为了保证非递减的特性，向下调整第一个元素不大于第二个元素即可
        // 比如4 2 3 那么第一步就应该调整4为2即 2 2 3（不要纠结调整为1等其他数字，这里调整的时候策略是相等，因为相等就满足非递减了）
        if(nums[0] > nums[1]){
            nums[0] = nums[1];
            count++;
        }
        for(int i=1;i+1<nums.length;i++){
            int left = nums[i-1];
            int right = nums[i+1];
            // 如果当前元素大于后面一个元素，那么需要分两种情况讨论
            // 比如1 4 3这种情况，为了保证非递减，只能调小第二个元素4，至少减为3才满足条件
            // 比如3 4 1这种情况，为了保证非递减，只能调大第三个元素3，至少增为4才满足条件
            if(nums[i] > right){
                // 先count++，判断count是否大于1了，大于1说明不止一处需要调整，直接返回false
                count++;
                if(count > 1){
                    return false;
                }
                // 对应3 4 1这种情况
                if(left > right){
                    nums[i+1] = nums[i];
                }else{
                    // 对应1 4 3这种情况
                    nums[i] = right;
                }
            }
        }
        return true;
    }
}