专栏首页chenjx85的技术专栏leetcode-665-Non-decreasing Array

leetcode-665-Non-decreasing Array

题目描述:

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10,000].

要完成的函数:

bool checkPossibility(vector<int>& nums) 

说明:

1、这道题目给定一个vector,要判断这个vector至多改变一个元素的值之后,是不是变成了非减序列。

首先笔者想的是,比如序列[1,4,2,3],这个序列改变4的值也就可以了,这样子的序列中间必然会有一个凸起,4就是这个凸起。

那我们可以先找到这个凸起,从前往后找跟从后往前找,如果只有一个凸起的话,那么就接着判断,如果有多个凸起,那么必定不能只改一个元素。

部分代码如下:

        int s1=nums.size();
        int i=0,j=s1-1;
        while(i<s1-1)
        {
            if(nums[i]<=nums[i+1])
                i++;
            else
                break;
        }
        if(i==j)//当整个序列非降序排列
            return true;
        while(j>i)
        {
            if(nums[j]>=nums[j-1])
                j--;
            else
                break;
        }
        if((j-1)!=i)//如果中间有多个元素
            return false;    

这样子就记录了i和j的值。

2、当确实只有一个凸起时,我们进行下一步判断。

还是以上面提到的序列为例子,[1,4,2,3],i=1,j=2,这个凸起的形成是由于nums[i]>nums[j],那我们可以改i这一位的值,也可以改j这一位的值,使得nums[i]<=nums[j]。

怎么判断什么时候要改i的值,什么时候要改j的值?

比如[3,4,2,5],i=1,j=2,这时候由于nums[i]的前一位3,大于nums[j]=2,所以我们只能修改j这一位的值,而不能修改i这一位的值。

那如果nums[i]的值,还是比nums[j]的下一位大呢,这时候我们就算修改j这一位的值,修改完也不能形成非减序列,这时候就要返回false。

如果nums[i]的值,小于等于nums[j]的下一位,那这时候就要返回true了。

还有另一种情况,如果nums[i]的前一位,小于等于nums[j],比如上面提到的[1,4,2,3],i=1,j=2,那这时候我们就可以修改i的值了,直接返回true即可。

代码如下:

        if(i!=0)
        {
            if(nums[i-1]>nums[j])//只能改j这一位
            {
                if(j==s1-1)
                    return true;
                if(nums[i]>nums[j+1])
                    return false;
                return true;
            }
            else
                return true;
        }
        return true;//如果i==0,那么直接修改nums[i]的值就可以了

上述代码虽然考虑的过程繁琐了点,但是实测38ms,beats 86.96% of cpp submissions,效果还是可以的。

3、附上完整代码,分享给大家,如下:

    bool checkPossibility(vector<int>& nums) 
    {
        int s1=nums.size();
        int i=0,j=s1-1;
        while(i<s1-1)
        {
            if(nums[i]<=nums[i+1])
                i++;
            else
                break;
        }
        if(i==j)
            return true;
        while(j>i)
        {
            if(nums[j]>=nums[j-1])
                j--;
            else
                break;
        }
        if((j-1)!=i)
            return false;
        if(i!=0)
        {
            if(nums[i-1]>nums[j])//只能改j这一位
            {
                if(j==s1-1)
                    return true;
                if(nums[i]>nums[j+1])
                    return false;
                return true;
            }
            elsereturn true;
        }
        return true; 
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-55-跳跃游戏

    1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

    chenjx85
  • leetcode-747-Largest Number At Least Twice of Others(求vector的最大值和次大值)

    chenjx85
  • leetcode-628-Maximum Product of Three Numbers

    chenjx85
  • Js算法与数据结构拾萃(1)

    算法是为了解决某些问题所提供的精确解法,数据结构是为了支撑算法提供的一种存储结构。

    一粒小麦
  • MaxSubarray最大子序和问题

    回顾leetcode原来做过的题,看到了经典的最大子序和问题,收藏了一个好回答。 这个问题是这样的(https://leetcode.com/problems...

    生信编程日常
  • leetcode-55-跳跃游戏

    1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

    chenjx85
  • leetCode刷题(找出数组里的两项相加等于定值)

    windseek
  • LeetCode【第217题】Contains Duplicate

    用户1432189
  • Leetcode 219. 存在重复元素 II

    给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为...

    zhipingChen
  • leetcode-747-Largest Number At Least Twice of Others(求vector的最大值和次大值)

    chenjx85

扫码关注云+社区

领取腾讯云代金券