[简单]665. 非递减数列

给定一个长度为 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。

重点:需要考虑到底要更改哪个位置的值这种情况。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数组是一种可变的、可索引的数据集合。在Scala中用Array[T]的形式来表示Java中的数组形式 T[]。 v...
    时待吾阅读 4,587评论 0 0
  • 1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不...
    曲终人散Li阅读 8,636评论 0 19
  • 题目描述 给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数...
    zhipingChen阅读 1,813评论 0 0
  • 排序算法说明 (1)排序的定义:对一序列对象根据某个关键字进行排序; 输入:n个数:a1,a2,a3,…,an 输...
    code武阅读 3,892评论 0 0
  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可...
    意识流丶阅读 8,406评论 2 9