给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。
思路:首先遍历数列,找到一个 array[i] > array[i + 1]的位置,说明这个位置是需要改变一个元素的。关键在于,改变一个元素之后,该序列是否是非递减序列。如果想要改变array[i],那么需要保证array[i+1]>=array[i-1],这样可以把array[i]变成array[i-1],继续向后判断。如果array[i+1]<array[i-1],那么只能改变array[i+1],将array[i+1]的值变为array[i],继续向后判断。如果i==0,那么将array[i]改为array[i+1]的值,继续向后判断,若再次发现一个需要更改的值,则返回false。
重点:需要考虑到底要更改哪个位置的值这种情况。