【LeetCode】非递减序列

题目

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

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

贪心

我们只有一次可以修改数组元素的机会 但是这里有一个修改的值为多少的问题
我们只有两种方式去修改
1.nums[i]=nums[i+1]
2.nums[i+1]=nums[i]

但是这两种方法也都是有不足的地方的
下面我给出两个极端的例子

所以我们还得动态考虑 就是nums[i-1]和nums[i+1]之间的比较

所以代码如下

 bool checkPossibility(vector<int>& nums) {
         if (nums.size() <= 2) return true;

    bool flag = true;

    for (int i = 0; i < nums.size() - 1; ++i)
    {
        if (nums[i] > nums[i + 1])
        {
            if (flag)
            {
                if (i == 0) nums[i] = nums[i + 1];
                else if (i > 0 && nums[i + 1] >= nums[i - 1])
                {
                    nums[i] = nums[i + 1];     //优先第一种方案
                }
                else
                {
                    nums[i + 1] = nums[i];    //万不得已第2种方案
                }
                flag = false;               //判断第几次修改
            }
            else
            {
                return false;
            }
        }
    }
    return true;
    }

希望我所写的对大家有所帮助

最后

以上就是风中玫瑰为你收集整理的【LeetCode】非递减序列的全部内容，希望文章能够帮你解决【LeetCode】非递减序列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。