665. 非递减数列 https://leetcode-cn.com/problems/non-decreasing-array/
给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。
class Solution {
public boolean checkPossibility(int[] nums) {
int len_num = nums.length;
if (len_num == 1) {
return true;
}
boolean[] low = new boolean[len_num];
boolean[] up = new boolean[len_num];
Arrays.fill(low, true);
Arrays.fill(up, true);
for (int i = 0; i < len_num; i++) {
if (i > 0) {
if (nums[i] >= nums[i - 1] && low[i - 1]) {
low[i] = true;
} else {
low[i] = false;
}
}
if (i < len_num - 1) {
if (nums[len_num - i - 2] <= nums[len_num - i - 1] && up[len_num - i - 1]) {
up[len_num - i - 2] = true;
}
else {
up[len_num - i - 2] = false;
}
}
}
for (int i = 0; i < len_num; i++) {
if (i == 0) {
if (up[i + 1]) {
return true;
}
} else if (i == len_num - 1) {
if (low[i - 1]) {
return true;
}
} else {
if (low[i - 1] && up[i + 1] && nums[i - 1] <= nums[i + 1]) {
return true;
}
}
}
return false;
}
}
根据题目的描述，我们定义了一个一个异常点的特征，这个点的右侧是递增，左侧是递增，而且右侧的数大于等于左侧的数，如果这个点让数组不递增，那么这个点就是一个异常点。本题就是需要寻找出所有的异常点，看看异常点的个数是否大于1.
在计算一个点左右侧是否递增的时候，可以把中间过程保存下来，减少计算次数。