LeetCode-非递减数队列

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

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

示例 1:

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

示例 2:

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

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

思路：
思考什么样的情况下改变一个数据能让一个数组为非递减数队列
第一种情况：乱序元素前后都是有序的，只有它一个乱序
第二种情况：乱序元素在队列的开头或结尾，其他数据也是有序的

代码：

class Solution {
    public boolean checkPossibility(int[] nums) {
        int i = 0,j = nums.length - 1;
        while(i < j && nums[i] <= nums[i + 1])
            i++;
        while(i < j && nums[j] >= nums[j - 1])
            j--;
        System.out.println(i + "----" + j); //找出乱序元素的位置
        int head = 0;
        if(i == 0)
            head = Integer.MIN_VALUE;//为零则乱序元素在开头位置
        else
            head = nums[i - 1];
        int next = (j==nums.length - 1)?Integer.MAX_VALUE:nums[j + 1];//最大为结尾位置
        if(j - i <= 1 && (head <= nums[j] || nums[i] <= next))//判断乱序元素是否只为一个，并是否有序
            return true;
        else
            return false;
    }
}